smatch_function_hooks.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  * There are several types of function hooks.
  20  *
  21  * The param_key hooks are probably the right things to use going forward.
  22  * They give you a name/sym pair so it means less code in the checks.
  23  *
  24  * The add_function_hook() functions are trigger for every call.  The
  25  * "return_implies" are triggered for specific return ranges.  The "exact"
  26  * variants will be triggered if it's *definitely* in the range where the
  27  * others will be triggered if it's *possibly* in the range.  The "late"
  28  * variants will be triggered after the others have run.
  29  *
  30  * There are a few miscellaneous things like add_function_assign_hook() and
  31  * add_macro_assign_hook() which are only triggered for assignments.  The
  32  * add_implied_return_hook() let's you manually adjust the return range.
  33  *
  34  * Every call:
  35  *     add_function_param_key_hook_early()
  36  *     add_function_param_key_hook()
  37  *     add_function_param_key_hook_late()
  38  *     add_function_hook_early()
  39  *     add_function_hook()
  40  *
  41  * Just for some return ranges:
  42  *     return_implies_param_key()
  43  *     return_implies_param_key_exact()
  44  *     return_implies_state()
  45  *     select_return_param_key()  (It's weird that this is not in smatch_db.c)
  46  *
  47  * For Assignments:
  48  *     add_function_assign_hook()
  49  *
  50  * For Macro Assignments:
  51  *     add_macro_assign_hook()
  52  *
  53  * Manipulate the return range.
  54  *     add_implied_return_hook()
  55  */
  56
  57 #include <stdlib.h>
  58 #include <stdio.h>
  59 #include <ctype.h>
  60 #include "smatch.h"
  61 #include "smatch_slist.h"
  62 #include "smatch_extra.h"
  63 #include "smatch_function_hashtable.h"
  64 #include "smatch_expression_stacks.h"
  65
  66 struct fcall_back {
  67         int type;
  68         struct data_range *range;
  69         union {
  70                 func_hook *call_back;
  71                 implication_hook *ranged;
  72                 implied_return_hook *implied_return;
  73         } u;
  74         void *info;
  75 };
  76
  77 ALLOCATOR(fcall_back, "call backs");
  78 DECLARE_PTR_LIST(call_back_list, struct fcall_back);
  79
  80 DEFINE_FUNCTION_HASHTABLE_STATIC(callback, struct fcall_back, struct call_back_list);
  81 static struct hashtable *func_hash;
  82
  83 int __in_fake_parameter_assign;
  84
  85 enum fn_hook_type {
  86         REGULAR_CALL_EARLY,
  87         REGULAR_CALL,
  88         REGULAR_CALL_LATE,
  89         RANGED_CALL,
  90         RANGED_EXACT,
  91         ASSIGN_CALL,
  92         IMPLIED_RETURN,
  93         MACRO_ASSIGN,
  94         MACRO_ASSIGN_EXTRA,
  95 };
  96
  97 struct param_key_data {
  98         param_key_hook *call_back;
  99         int param;
 100         const char *key;
 101         void *info;
 102 };
 103
 104 struct return_implies_callback {
 105         int type;
 106         bool param_key;
 107         union {
 108                 return_implies_hook *callback;
 109                 param_key_hook *pk_callback;
 110         };
 111 };
 112 ALLOCATOR(return_implies_callback, "return_implies callbacks");
 113 DECLARE_PTR_LIST(db_implies_list, struct return_implies_callback);
 114 static struct db_implies_list *db_return_states_list;
 115
 116 static struct void_fn_list *return_states_before;
 117 static struct void_fn_list *return_states_after;
 118 static struct string_hook_list *return_string_hooks;
 119
 120 struct db_callback_info {
 121         int true_side;
 122         int comparison;
 123         struct expression *expr;
 124         struct range_list *rl;
 125         int left;
 126         struct stree *stree;
 127         struct stree *implied;
 128         struct db_implies_list *callbacks;
 129         struct db_implies_list *called;
 130         int prev_return_id;
 131         int cull;
 132         int has_states;
 133         char *ret_str;
 134         struct smatch_state *ret_state;
 135         struct expression *var_expr;
 136         struct expression_list *fake_param_assign_stack;
 137         int handled;
 138 };
 139
 140 static struct expression_list *fake_calls;
 141
 142 void add_fake_call_after_return(struct expression *call)
 143 {
 144         add_ptr_list(&fake_calls, call);
 145 }
 146
 147 static void parse_fake_calls(void)
 148 {
 149         struct expression_list *list;
 150         struct expression *call;
 151
 152         list = fake_calls;
 153         fake_calls = NULL;
 154
 155         FOR_EACH_PTR(list, call) {
 156                 __split_expr(call);
 157         } END_FOR_EACH_PTR(call);
 158
 159         __free_ptr_list((struct ptr_list **)&list);
 160 }
 161
 162 static struct fcall_back *alloc_fcall_back(int type, void *call_back,
 163                                            void *info)
 164 {
 165         struct fcall_back *cb;
 166
 167         cb = __alloc_fcall_back(0);
 168         cb->type = type;
 169         cb->u.call_back = call_back;
 170         cb->info = info;
 171         return cb;
 172 }
 173
 174 static const char *get_fn_name(struct expression *fn)
 175 {
 176         fn = strip_expr(fn);
 177         if (!fn)
 178                 return NULL;
 179         if (fn->type == EXPR_SYMBOL && fn->symbol)
 180                 return fn->symbol->ident->name;
 181         return get_member_name(fn);
 182 }
 183
 184 static struct call_back_list *get_call_backs(const char *fn_name)
 185 {
 186         if (!fn_name)
 187                 return NULL;
 188         return search_callback(func_hash, (char *)fn_name);
 189 }
 190
 191 void add_function_hook(const char *look_for, func_hook *call_back, void *info)
 192 {
 193         struct fcall_back *cb;
 194
 195         cb = alloc_fcall_back(REGULAR_CALL, call_back, info);
 196         add_callback(func_hash, look_for, cb);
 197 }
 198
 199 void add_function_hook_early(const char *look_for, func_hook *call_back, void *info)
 200 {
 201         struct fcall_back *cb;
 202
 203         cb = alloc_fcall_back(REGULAR_CALL_EARLY, call_back, info);
 204         add_callback(func_hash, look_for, cb);
 205 }
 206
 207 void add_function_hook_late(const char *look_for, func_hook *call_back, void *info)
 208 {
 209         struct fcall_back *cb;
 210
 211         cb = alloc_fcall_back(REGULAR_CALL_LATE, call_back, info);
 212         add_callback(func_hash, look_for, cb);
 213 }
 214
 215 void add_function_assign_hook(const char *look_for, func_hook *call_back,
 216                               void *info)
 217 {
 218         struct fcall_back *cb;
 219
 220         cb = alloc_fcall_back(ASSIGN_CALL, call_back, info);
 221         add_callback(func_hash, look_for, cb);
 222 }
 223
 224 static void register_funcs_from_file_helper(const char *file,
 225                                             func_hook *call_back, void *info,
 226                                             bool assign)
 227 {
 228         struct token *token;
 229         const char *func;
 230         char name[64];
 231
 232         snprintf(name, sizeof(name), "%s.%s", option_project_str, file);
 233         token = get_tokens_file(name);
 234         if (!token)
 235                 return;
 236         if (token_type(token) != TOKEN_STREAMBEGIN)
 237                 return;
 238         token = token->next;
 239         while (token_type(token) != TOKEN_STREAMEND) {
 240                 if (token_type(token) != TOKEN_IDENT)
 241                         return;
 242                 func = show_ident(token->ident);
 243                 if (assign)
 244                         add_function_assign_hook(func, call_back, info);
 245                 else
 246                         add_function_hook(func, call_back, info);
 247                 token = token->next;
 248         }
 249         clear_token_alloc();
 250 }
 251
 252 void register_func_hooks_from_file(const char *file,
 253                                    func_hook *call_back, void *info)
 254 {
 255         register_funcs_from_file_helper(file, call_back, info, false);
 256 }
 257
 258 void register_assign_hooks_from_file(const char *file,
 259                                      func_hook *call_back, void *info)
 260 {
 261         register_funcs_from_file_helper(file, call_back, info, true);
 262 }
 263
 264 void add_implied_return_hook(const char *look_for,
 265                              implied_return_hook *call_back,
 266                              void *info)
 267 {
 268         struct fcall_back *cb;
 269
 270         cb = alloc_fcall_back(IMPLIED_RETURN, call_back, info);
 271         add_callback(func_hash, look_for, cb);
 272 }
 273
 274 static void db_helper(struct expression *expr, param_key_hook *call_back, int param, const char *key, void *info)
 275 {
 276         char *name;
 277         struct symbol *sym;
 278
 279         if (param == -2) {
 280                 call_back(expr, key, NULL, info);
 281                 return;
 282         }
 283
 284         name = get_name_sym_from_param_key(expr, param, key, &sym);
 285         if (!name || !sym)
 286                 goto free;
 287
 288         call_back(expr, name, sym, info);
 289 free:
 290         free_string(name);
 291 }
 292
 293 static struct expression *get_parent_assignment(struct expression *expr)
 294 {
 295         struct expression *parent;
 296         int cnt = 0;
 297
 298         if (expr->type == EXPR_ASSIGNMENT)
 299                 return NULL;
 300
 301         parent = expr_get_fake_parent_expr(expr);
 302         if (parent && parent->type == EXPR_ASSIGNMENT)
 303                 return parent;
 304
 305         parent = expr;
 306         while (true) {
 307                 parent = expr_get_parent_expr(parent);
 308                 if (!parent || ++cnt >= 5)
 309                         break;
 310                 if (parent->type == EXPR_CAST)
 311                         continue;
 312                 if (parent->type == EXPR_PREOP && parent->op == '(')
 313                         continue;
 314                 break;
 315         }
 316
 317         if (parent && parent->type == EXPR_ASSIGNMENT)
 318                 return parent;
 319         return NULL;
 320 }
 321
 322 static void param_key_function(const char *fn, struct expression *expr, void *data)
 323 {
 324         struct param_key_data *pkd = data;
 325         struct expression *parent;
 326
 327         parent = get_parent_assignment(expr);
 328         if (parent)
 329                 expr = parent;
 330
 331         db_helper(expr, pkd->call_back, pkd->param, pkd->key, pkd->info);
 332 }
 333
 334 static void param_key_implies_function(const char *fn, struct expression *call_expr,
 335                                        struct expression *assign_expr, void *data)
 336 {
 337         struct param_key_data *pkd = data;
 338
 339         db_helper(assign_expr ?: call_expr, pkd->call_back, pkd->param, pkd->key, pkd->info);
 340 }
 341
 342 static struct param_key_data *alloc_pkd(param_key_hook *call_back, int param, const char *key, void *info)
 343 {
 344         struct param_key_data *pkd;
 345
 346         pkd = malloc(sizeof(*pkd));
 347         pkd->call_back = call_back;
 348         pkd->param = param;
 349         pkd->key = alloc_string(key);
 350         pkd->info = info;
 351
 352         return pkd;
 353 }
 354
 355 void add_function_param_key_hook_early(const char *look_for, param_key_hook *call_back,
 356                                        int param, const char *key, void *info)
 357 {
 358         struct param_key_data *pkd;
 359
 360         if (param == -1) {
 361                 printf("pointless early hook for '%s'", look_for);
 362                 return;
 363         }
 364
 365         pkd = alloc_pkd(call_back, param, key, info);
 366         add_function_hook_early(look_for, &param_key_function, pkd);
 367 }
 368
 369 void add_function_param_key_hook(const char *look_for, param_key_hook *call_back,
 370                                  int param, const char *key, void *info)
 371 {
 372         struct param_key_data *pkd;
 373
 374         pkd = alloc_pkd(call_back, param, key, info);
 375         if (param == -1)
 376                 add_function_assign_hook(look_for, &param_key_function, pkd);
 377         else
 378                 add_function_hook(look_for, &param_key_function, pkd);
 379 }
 380
 381 void add_function_param_key_hook_late(const char *look_for, param_key_hook *call_back,
 382                                       int param, const char *key, void *info)
 383 {
 384         struct param_key_data *pkd;
 385
 386         pkd = alloc_pkd(call_back, param, key, info);
 387         add_function_hook_late(look_for, &param_key_function, pkd);
 388 }
 389
 390 void return_implies_param_key(const char *look_for, sval_t start, sval_t end,
 391                               param_key_hook *call_back,
 392                               int param, const char *key, void *info)
 393 {
 394         struct param_key_data *pkd;
 395
 396         pkd = alloc_pkd(call_back, param, key, info);
 397         return_implies_state_sval(look_for, start, end, &param_key_implies_function, pkd);
 398 }
 399
 400 void return_implies_param_key_exact(const char *look_for, sval_t start, sval_t end,
 401                                     param_key_hook *call_back,
 402                                     int param, const char *key, void *info)
 403 {
 404         struct param_key_data *pkd;
 405
 406         pkd = alloc_pkd(call_back, param, key, info);
 407         return_implies_exact(look_for, start, end, &param_key_implies_function, pkd);
 408 }
 409
 410 void add_macro_assign_hook(const char *look_for, func_hook *call_back,
 411                         void *info)
 412 {
 413         struct fcall_back *cb;
 414
 415         cb = alloc_fcall_back(MACRO_ASSIGN, call_back, info);
 416         add_callback(func_hash, look_for, cb);
 417 }
 418
 419 void add_macro_assign_hook_extra(const char *look_for, func_hook *call_back,
 420                         void *info)
 421 {
 422         struct fcall_back *cb;
 423
 424         cb = alloc_fcall_back(MACRO_ASSIGN_EXTRA, call_back, info);
 425         add_callback(func_hash, look_for, cb);
 426 }
 427
 428 void return_implies_state(const char *look_for, long long start, long long end,
 429                          implication_hook *call_back, void *info)
 430 {
 431         struct fcall_back *cb;
 432
 433         cb = alloc_fcall_back(RANGED_CALL, call_back, info);
 434         cb->range = alloc_range_perm(ll_to_sval(start), ll_to_sval(end));
 435         add_callback(func_hash, look_for, cb);
 436 }
 437
 438 void return_implies_state_sval(const char *look_for, sval_t start, sval_t end,
 439                          implication_hook *call_back, void *info)
 440 {
 441         struct fcall_back *cb;
 442
 443         cb = alloc_fcall_back(RANGED_CALL, call_back, info);
 444         cb->range = alloc_range_perm(start, end);
 445         add_callback(func_hash, look_for, cb);
 446 }
 447
 448 void return_implies_exact(const char *look_for, sval_t start, sval_t end,
 449                           implication_hook *call_back, void *info)
 450 {
 451         struct fcall_back *cb;
 452
 453         cb = alloc_fcall_back(RANGED_EXACT, call_back, info);
 454         cb->range = alloc_range_perm(start, end);
 455         add_callback(func_hash, look_for, cb);
 456 }
 457
 458 static struct return_implies_callback *alloc_db_return_callback(int type, bool param_key, void *callback)
 459 {
 460         struct return_implies_callback *cb;
 461
 462         cb = __alloc_return_implies_callback(0);
 463         cb->type = type;
 464         cb->param_key = param_key;
 465         cb->callback = callback;
 466
 467         return cb;
 468 }
 469
 470 void select_return_states_hook(int type, return_implies_hook *callback)
 471 {
 472         struct return_implies_callback *cb;
 473
 474         cb = alloc_db_return_callback(type, false, callback);
 475         add_ptr_list(&db_return_states_list, cb);
 476 }
 477
 478 static void call_db_return_callback(struct db_callback_info *db_info,
 479                                     struct return_implies_callback *cb,
 480                                     int param, char *key, char *value)
 481 {
 482         if (cb->param_key) {
 483                 db_helper(db_info->expr, cb->pk_callback, param, key, NULL);
 484                 add_ptr_list(&db_info->called, cb);
 485         } else {
 486                 cb->callback(db_info->expr, param, key, value);
 487         }
 488 }
 489
 490 void select_return_param_key(int type, param_key_hook *callback)
 491 {
 492         struct return_implies_callback *cb;
 493
 494         cb = alloc_db_return_callback(type, true, callback);
 495         add_ptr_list(&db_return_states_list, cb);
 496 }
 497
 498 void select_return_states_before(void_fn *fn)
 499 {
 500         add_ptr_list(&return_states_before, fn);
 501 }
 502
 503 void select_return_states_after(void_fn *fn)
 504 {
 505         add_ptr_list(&return_states_after, fn);
 506 }
 507
 508 void add_return_string_hook(string_hook *fn)
 509 {
 510         add_ptr_list(&return_string_hooks, fn);
 511 }
 512
 513 static bool call_call_backs(struct call_back_list *list, int type,
 514                             const char *fn, struct expression *expr)
 515 {
 516         struct fcall_back *tmp;
 517         bool handled = false;
 518
 519         FOR_EACH_PTR(list, tmp) {
 520                 if (tmp->type == type) {
 521                         (tmp->u.call_back)(fn, expr, tmp->info);
 522                         handled = true;
 523                 }
 524         } END_FOR_EACH_PTR(tmp);
 525
 526         return handled;
 527 }
 528
 529 static void call_function_hooks(struct expression *expr, enum fn_hook_type type)
 530 {
 531         struct call_back_list *call_backs;
 532         const char *fn_name;
 533
 534         while (expr->type == EXPR_ASSIGNMENT)
 535                 expr = strip_expr(expr->right);
 536         if (expr->type != EXPR_CALL)
 537                 return;
 538
 539         fn_name = get_fn_name(expr->fn);
 540         call_backs = get_call_backs(fn_name);
 541         if (!call_backs)
 542                 return;
 543
 544         call_call_backs(call_backs, type, fn_name, expr);
 545 }
 546
 547 static void call_return_states_after_hooks(struct expression *expr)
 548 {
 549         call_void_fns(return_states_after);
 550         __pass_to_client(expr, FUNCTION_CALL_HOOK_AFTER_DB);
 551         call_function_hooks(expr, REGULAR_CALL_LATE);
 552 }
 553
 554 static void call_ranged_call_backs(struct call_back_list *list,
 555                                 const char *fn, struct expression *call_expr,
 556                                 struct expression *assign_expr)
 557 {
 558         struct fcall_back *tmp;
 559
 560         FOR_EACH_PTR(list, tmp) {
 561                 (tmp->u.ranged)(fn, call_expr, assign_expr, tmp->info);
 562         } END_FOR_EACH_PTR(tmp);
 563 }
 564
 565 static struct call_back_list *get_same_ranged_call_backs(struct call_back_list *list,
 566                                                 struct data_range *drange)
 567 {
 568         struct call_back_list *ret = NULL;
 569         struct fcall_back *tmp;
 570
 571         FOR_EACH_PTR(list, tmp) {
 572                 if (tmp->type != RANGED_CALL &&
 573                     tmp->type != RANGED_EXACT)
 574                         continue;
 575                 if (ranges_equiv(tmp->range, drange))
 576                         add_ptr_list(&ret, tmp);
 577         } END_FOR_EACH_PTR(tmp);
 578         return ret;
 579 }
 580
 581 static bool in_list_exact_sval(struct range_list *list, struct data_range *drange)
 582 {
 583         struct data_range *tmp;
 584
 585         FOR_EACH_PTR(list, tmp) {
 586                 if (ranges_equiv(tmp, drange))
 587                         return true;
 588         } END_FOR_EACH_PTR(tmp);
 589         return false;
 590 }
 591
 592 /*
 593  * The assign_ranged_funcs() function is called when we have no data from the DB.
 594  */
 595 static bool assign_ranged_funcs(const char *fn, struct expression *expr,
 596                                  struct call_back_list *call_backs)
 597 {
 598         struct fcall_back *tmp;
 599         struct sm_state *sm;
 600         char *var_name;
 601         struct symbol *sym;
 602         struct smatch_state *estate;
 603         struct stree *tmp_stree;
 604         struct stree *final_states = NULL;
 605         struct range_list *handled_ranges = NULL;
 606         struct range_list *unhandled_rl;
 607         struct call_back_list *same_range_call_backs = NULL;
 608         struct expression *call;
 609         struct range_list *rl;
 610         int handled = false;
 611
 612         if (!call_backs)
 613                 return false;
 614
 615         var_name = expr_to_var_sym(expr->left, &sym);
 616         if (!var_name || !sym)
 617                 goto free;
 618
 619         call = strip_expr(expr->right);
 620
 621         FOR_EACH_PTR(call_backs, tmp) {
 622                 if (tmp->type != RANGED_CALL &&
 623                     tmp->type != RANGED_EXACT)
 624                         continue;
 625
 626                 if (in_list_exact_sval(handled_ranges, tmp->range))
 627                         continue;
 628                 __push_fake_cur_stree();
 629                 tack_on(&handled_ranges, tmp->range);
 630
 631                 same_range_call_backs = get_same_ranged_call_backs(call_backs, tmp->range);
 632                 call_ranged_call_backs(same_range_call_backs, fn, expr->right, expr);
 633                 __free_ptr_list((struct ptr_list **)&same_range_call_backs);
 634
 635                 rl = alloc_rl(tmp->range->min, tmp->range->max);
 636                 rl = cast_rl(get_type(expr->left), rl);
 637                 estate = alloc_estate_rl(rl);
 638                 set_extra_mod(var_name, sym, expr->left, estate);
 639
 640                 tmp_stree = __pop_fake_cur_stree();
 641                 merge_fake_stree(&final_states, tmp_stree);
 642                 free_stree(&tmp_stree);
 643                 handled = true;
 644         } END_FOR_EACH_PTR(tmp);
 645
 646         unhandled_rl = rl_filter(alloc_whole_rl(get_type(call)), handled_ranges);
 647         if (unhandled_rl) {
 648                 __push_fake_cur_stree();
 649                 rl = cast_rl(get_type(expr->left), unhandled_rl);
 650                 estate = alloc_estate_rl(rl);
 651                 set_extra_mod(var_name, sym, expr->left, estate);
 652                 tmp_stree = __pop_fake_cur_stree();
 653                 merge_fake_stree(&final_states, tmp_stree);
 654                 free_stree(&tmp_stree);
 655         }
 656
 657         FOR_EACH_SM(final_states, sm) {
 658                 __set_sm(sm);
 659         } END_FOR_EACH_SM(sm);
 660
 661         free_stree(&final_states);
 662 free:
 663         free_string(var_name);
 664         return handled;
 665 }
 666
 667 static void call_implies_callbacks(int comparison, struct expression *expr, sval_t sval, int left, struct stree **implied_true, struct stree **implied_false)
 668 {
 669         struct call_back_list *call_backs;
 670         struct fcall_back *tmp;
 671         const char *fn_name;
 672         struct data_range *value_range;
 673         struct stree *true_states = NULL;
 674         struct stree *false_states = NULL;
 675         struct stree *tmp_stree;
 676
 677         *implied_true = NULL;
 678         *implied_false = NULL;
 679         fn_name = get_fn_name(expr->fn);
 680         call_backs = get_call_backs(fn_name);
 681         if (!call_backs)
 682                 return;
 683         value_range = alloc_range(sval, sval);
 684
 685         /* set true states */
 686         __push_fake_cur_stree();
 687         FOR_EACH_PTR(call_backs, tmp) {
 688                 if (tmp->type != RANGED_CALL &&
 689                     tmp->type != RANGED_EXACT)
 690                         continue;
 691                 if (!true_comparison_range_LR(comparison, tmp->range, value_range, left))
 692                         continue;
 693                 (tmp->u.ranged)(fn_name, expr, NULL, tmp->info);
 694         } END_FOR_EACH_PTR(tmp);
 695         tmp_stree = __pop_fake_cur_stree();
 696         merge_fake_stree(&true_states, tmp_stree);
 697         free_stree(&tmp_stree);
 698
 699         /* set false states */
 700         __push_fake_cur_stree();
 701         FOR_EACH_PTR(call_backs, tmp) {
 702                 if (tmp->type != RANGED_CALL &&
 703                     tmp->type != RANGED_EXACT)
 704                         continue;
 705                 if (!false_comparison_range_LR(comparison, tmp->range, value_range, left))
 706                         continue;
 707                 (tmp->u.ranged)(fn_name, expr, NULL, tmp->info);
 708         } END_FOR_EACH_PTR(tmp);
 709         tmp_stree = __pop_fake_cur_stree();
 710         merge_fake_stree(&false_states, tmp_stree);
 711         free_stree(&tmp_stree);
 712
 713         *implied_true = true_states;
 714         *implied_false = false_states;
 715 }
 716
 717 static void set_implied_states(struct db_callback_info *db_info)
 718 {
 719         struct sm_state *sm;
 720
 721         FOR_EACH_SM(db_info->implied, sm) {
 722                 __set_sm(sm);
 723         } END_FOR_EACH_SM(sm);
 724
 725         free_stree(&db_info->implied);
 726 }
 727
 728 static void store_return_state(struct db_callback_info *db_info, const char *ret_str, struct smatch_state *state)
 729 {
 730         db_info->ret_str = alloc_sname(ret_str),
 731         db_info->ret_state = state;
 732 }
 733
 734 static struct expression_list *unfaked_calls;
 735
 736 struct expression *get_unfaked_call(void)
 737 {
 738         return last_ptr_list((struct ptr_list *)unfaked_calls);
 739 }
 740
 741 static void store_unfaked_call(struct expression *expr)
 742 {
 743         push_expression(&unfaked_calls, expr);
 744 }
 745
 746 static void clear_unfaked_call(void)
 747 {
 748         delete_ptr_list_last((struct ptr_list **)&unfaked_calls);
 749 }
 750
 751 void fake_param_assign_helper(struct expression *call, struct expression *fake_assign)
 752 {
 753         store_unfaked_call(call);
 754         __in_fake_parameter_assign++;
 755         __split_expr(fake_assign);
 756         __in_fake_parameter_assign--;
 757         clear_unfaked_call();
 758 }
 759
 760 static bool fake_a_param_assignment(struct expression *expr, const char *ret_str, struct smatch_state *orig)
 761 {
 762         struct expression *arg, *left, *right, *tmp, *fake_assign;
 763         char *p;
 764         int param;
 765         char buf[256];
 766         char *str;
 767
 768         if (expr->type != EXPR_ASSIGNMENT || expr->op != '=')
 769                 return false;
 770         left = expr->left;
 771         right = expr->right;
 772
 773         while (right->type == EXPR_ASSIGNMENT)
 774                 right = strip_expr(right->right);
 775         if (!right || right->type != EXPR_CALL)
 776                 return false;
 777
 778         p = strchr(ret_str, '[');
 779         if (!p)
 780                 return false;
 781
 782         p++;
 783         if (p[0] == '=' && p[1] == '=')
 784                 p += 2;
 785         if (p[0] != '$')
 786                 return false;
 787
 788         snprintf(buf, sizeof(buf), "%s", p);
 789
 790         p = buf;
 791         p += 1;
 792         param = strtol(p, &p, 10);
 793
 794         p = strchr(p, ']');
 795         if (!p || *p != ']')
 796                 return false;
 797         *p = '\0';
 798
 799         arg = get_argument_from_call_expr(right->args, param);
 800         if (!arg)
 801                 return false;
 802
 803         /* There should be a get_other_name() function which returns an expr */
 804         tmp = get_assigned_expr(arg);
 805         if (tmp)
 806                 arg = tmp;
 807
 808         /*
 809          * This is a sanity check to prevent side effects from evaluating stuff
 810          * twice.
 811          */
 812         str = expr_to_chunk_sym_vsl(arg, NULL, NULL);
 813         if (!str)
 814                 return false;
 815         free_string(str);
 816
 817         right = gen_expression_from_key(arg, buf);
 818         if (!right)  /* Mostly fails for binops like [$0 + 4032] */
 819                 return false;
 820         fake_assign = assign_expression(left, '=', right);
 821         fake_param_assign_helper(expr, fake_assign);
 822
 823         /*
 824          * If the return is "0-65531[$0->nla_len - 4]" the faked expression
 825          * is maybe (-4)-65531 but we know it is in the 0-65531 range so both
 826          * parts have to be considered.  We use _nomod() because it's not really
 827          * another modification, it's just a clarification.
 828          *
 829          */
 830         if (estate_rl(orig)) {
 831                 struct smatch_state *faked;
 832                 struct range_list *rl;
 833
 834                 faked = get_extra_state(left);
 835                 if (estate_rl(faked)) {
 836                         rl = rl_intersection(estate_rl(faked), estate_rl(orig));
 837                         if (rl)
 838                                 set_extra_expr_nomod(left, alloc_estate_rl(rl));
 839                 }
 840         }
 841
 842         return true;
 843 }
 844
 845 static void fake_return_assignment(struct db_callback_info *db_info, int type, int param, char *key, char *value)
 846 {
 847         struct expression *call, *left, *right, *assign;
 848         int right_param;
 849
 850         if (type != PARAM_COMPARE)
 851                 return;
 852
 853         call = db_info->expr;
 854         while (call && call->type == EXPR_ASSIGNMENT)
 855                 call = strip_expr(call->right);
 856         if (!call || call->type != EXPR_CALL)
 857                 return;
 858
 859         // TODO: This only handles "$->foo = arg" and not "$->foo = arg->bar".
 860         if (param != -1)
 861                 return;
 862         if (!value || strncmp(value, "== $", 4) != 0)
 863                 return;
 864         if (!isdigit(value[4]) || value[5] != '\0')
 865                 return;
 866         right_param = atoi(value + 4);
 867
 868         left = gen_expr_from_param_key(db_info->expr, param, key);
 869         if (!left)
 870                 return;
 871         right = get_argument_from_call_expr(call->args, right_param);
 872
 873         assign = assign_expression(left, '=', right);
 874         push_expression(&db_info->fake_param_assign_stack, assign);
 875 }
 876
 877 static void set_fresh_mtag_returns(struct db_callback_info *db_info)
 878 {
 879         struct expression *expr;
 880         struct smatch_state *state;
 881
 882         if (!db_info->ret_state)
 883                 return;
 884
 885         if (!db_info->expr ||
 886             db_info->expr->type != EXPR_ASSIGNMENT ||
 887             db_info->expr->op != '=')
 888                 return;
 889
 890         expr = db_info->expr->left;
 891
 892         state = alloc_estate_rl(cast_rl(get_type(expr), clone_rl(estate_rl(db_info->ret_state))));
 893         state = get_mtag_return(db_info->expr, state);
 894         if (!state)
 895                 return;
 896
 897         set_real_absolute(expr, state);
 898         set_extra_expr_mod(expr, state);
 899 }
 900
 901 static void set_return_assign_state(struct db_callback_info *db_info)
 902 {
 903         struct expression *expr = db_info->expr->left;
 904         struct expression *fake_assign;
 905         struct smatch_state *state;
 906
 907         if (!db_info->ret_state)
 908                 return;
 909
 910         state = alloc_estate_rl(cast_rl(get_type(expr), clone_rl(estate_rl(db_info->ret_state))));
 911         if (!fake_a_param_assignment(db_info->expr, db_info->ret_str, state))
 912                 set_extra_expr_mod(expr, state);
 913
 914         while ((fake_assign = pop_expression(&db_info->fake_param_assign_stack))) {
 915                 struct range_list *left, *right;
 916
 917                 /*
 918                  * Originally, I tried to do this as a assignment to record that
 919                  * a = frob(b) implies that "a->foo == b->foo" etc.  But that
 920                  * caused a problem because then it was recorded that "a->foo"
 921                  * was modified and recorded as a PARAM_SET in the database.
 922                  *
 923                  * So now, instead of faking an assignment we use
 924                  * set_extra_expr_nomod() but it's still recorded as an
 925                  * assignment in the ->fake_param_assign_stack for legacy
 926                  * reasons and because it's a handy way to store a left/right
 927                  * pair.
 928                  */
 929
 930                 get_absolute_rl(fake_assign->left, &left);
 931                 get_absolute_rl(fake_assign->right, &right);
 932                 right = cast_rl(get_type(fake_assign->left), right);
 933                 // FIXME: add some sanity checks
 934                 // FIXME: preserve the sm state if possible
 935                 set_extra_expr_nomod(fake_assign->left, alloc_estate_rl(right));
 936         }
 937 }
 938
 939 static void set_other_side_state(struct db_callback_info *db_info)
 940 {
 941         struct expression *expr = db_info->var_expr;
 942         struct smatch_state *state;
 943
 944         if (!db_info->ret_state)
 945                 return;
 946
 947         // TODO: faked_assign set ==$ equiv here
 948
 949         state = alloc_estate_rl(cast_rl(get_type(expr), clone_rl(estate_rl(db_info->ret_state))));
 950         set_extra_expr_nomod(expr, state);
 951         db_info->ret_state = NULL;
 952         db_info->ret_str = NULL;
 953 }
 954
 955 static void handle_ret_equals_param(char *ret_string, struct range_list *rl, struct expression *call)
 956 {
 957         char *str;
 958         long long param;
 959         struct expression *arg;
 960         struct range_list *orig;
 961
 962         // TODO: faked_assign This needs to be handled in the assignment code
 963
 964         str = strstr(ret_string, "==$");
 965         if (!str)
 966                 return;
 967         str += 3;
 968         param = strtoll(str, NULL, 10);
 969         arg = get_argument_from_call_expr(call->args, param);
 970         if (!arg)
 971                 return;
 972         get_absolute_rl(arg, &orig);
 973         rl = rl_intersection(orig, rl);
 974         if (!rl)
 975                 return;
 976         set_extra_expr_nomod(arg, alloc_estate_rl(rl));
 977 }
 978
 979 static bool impossible_limit(struct db_callback_info *db_info, int param, char *key, char *value)
 980 {
 981         struct expression *expr = db_info->expr;
 982         struct expression *arg;
 983         struct smatch_state *state;
 984         struct range_list *passed;
 985         struct range_list *limit;
 986         struct symbol *compare_type;
 987
 988         while (expr->type == EXPR_ASSIGNMENT)
 989                 expr = strip_expr(expr->right);
 990         if (expr->type != EXPR_CALL)
 991                 return false;
 992
 993         arg = get_argument_from_call_expr(expr->args, param);
 994         if (!arg)
 995                 return false;
 996
 997         if (strcmp(key, "$") == 0) {
 998                 if (!get_implied_rl(arg, &passed))
 999                         return false;
1000
1001                 compare_type = get_arg_type(expr->fn, param);
1002         } else {
1003                 char *name;
1004                 struct symbol *sym;
1005
1006                 name = get_variable_from_key(arg, key, &sym);
1007                 if (!name || !sym)
1008                         return false;
1009
1010                 state = get_state(SMATCH_EXTRA, name, sym);
1011                 if (!state) {
1012                         free_string(name);
1013                         return false;
1014                 }
1015                 passed = estate_rl(state);
1016                 if (!passed || is_whole_rl(passed)) {
1017                         free_string(name);
1018                         return false;
1019                 }
1020
1021                 compare_type = get_member_type_from_key(arg, key);
1022         }
1023
1024         passed = cast_rl(compare_type, passed);
1025         call_results_to_rl(expr, compare_type, value, &limit);
1026         if (!limit || is_whole_rl(limit))
1027                 return false;
1028         if (possibly_true_rl(passed, SPECIAL_EQUAL, limit))
1029                 return false;
1030         if (option_debug || local_debug || debug_db)
1031                 sm_msg("impossible: %d '%s' limit '%s' == '%s' return='%s'", param, key, show_rl(passed), value, db_info->ret_str);
1032         return true;
1033 }
1034
1035 static bool is_impossible_data(int type, struct db_callback_info *db_info, int param, char *key, char *value)
1036 {
1037         if (type == PARAM_LIMIT && impossible_limit(db_info, param, key, value))
1038                 return true;
1039         if (type == COMPARE_LIMIT && param_compare_limit_is_impossible(db_info->expr, param, key, value)) {
1040                 if (local_debug || debug_db)
1041                         sm_msg("param_compare_limit_is_impossible: %d %s %s", param, key, value);
1042                 return true;
1043         }
1044         return false;
1045 }
1046
1047 static bool func_type_mismatch(struct expression *expr, const char *value)
1048 {
1049         struct symbol *type;
1050
1051         /* This makes faking returns easier */
1052         if (!value || value[0] == '\0')
1053                 return false;
1054
1055         while (expr->type == EXPR_ASSIGNMENT)
1056                 expr = strip_expr(expr->right);
1057
1058         /*
1059          * Short cut:  We only care about function pointers that are struct
1060          * members.
1061          *
1062          */
1063         if (expr->fn->type == EXPR_SYMBOL)
1064                 return false;
1065
1066         type = get_type(expr->fn);
1067         if (!type)
1068                 return false;
1069         if (type->type == SYM_PTR)
1070                 type = get_real_base_type(type);
1071
1072         if (strcmp(type_to_str(type), value) == 0)
1073                 return false;
1074
1075         return true;
1076 }
1077
1078 static void process_return_states(struct db_callback_info *db_info)
1079 {
1080         struct stree *stree;
1081
1082         set_implied_states(db_info);
1083         set_fresh_mtag_returns(db_info);
1084         parse_fake_calls();
1085         free_ptr_list(&db_info->called);
1086         stree = __pop_fake_cur_stree();
1087         if (debug_db) {
1088                 sm_msg("States from DB: %s expr='%s' ret_str='%s' rl='%s' state='%s'",
1089                        db_info->cull ? "Culling" : "Merging",
1090                        expr_to_str(db_info->expr),
1091                        db_info->ret_str, show_rl(db_info->rl),
1092                        db_info->ret_state ? db_info->ret_state->name : "<none>");
1093                 __print_stree(stree);
1094         }
1095
1096         if (!db_info->cull)
1097                 merge_fake_stree(&db_info->stree, stree);
1098         free_stree(&stree);
1099
1100         db_info->ret_state = NULL;
1101         db_info->ret_str = NULL;
1102 }
1103
1104 static int db_compare_callback(void *_info, int argc, char **argv, char **azColName)
1105 {
1106         struct db_callback_info *db_info = _info;
1107         struct range_list *var_rl = db_info->rl;
1108         struct range_list *ret_range;
1109         int type, param;
1110         char *ret_str, *key, *value;
1111         struct return_implies_callback *tmp;
1112         int return_id;
1113         int comparison;
1114
1115         if (argc != 6)
1116                 return 0;
1117
1118         return_id = atoi(argv[0]);
1119         ret_str = argv[1];
1120         type = atoi(argv[2]);
1121         param = atoi(argv[3]);
1122         key = argv[4];
1123         value = argv[5];
1124
1125         db_info->has_states = 1;
1126         if (db_info->prev_return_id != -1 && type == INTERNAL) {
1127                 set_other_side_state(db_info);
1128                 process_return_states(db_info);
1129                 __push_fake_cur_stree();
1130                 db_info->cull = 0;
1131         }
1132         db_info->prev_return_id = return_id;
1133
1134         if (type == INTERNAL && func_type_mismatch(db_info->expr, value))
1135                 db_info->cull = 1;
1136         if (db_info->cull)
1137                 return 0;
1138         if (type == CULL_PATH) {
1139                 db_info->cull = 1;
1140                 return 0;
1141         }
1142
1143         if (is_impossible_data(type, db_info, param, key, value)) {
1144                 db_info->cull = 1;
1145                 return 0;
1146         }
1147
1148         call_results_to_rl(db_info->expr, get_type(strip_expr(db_info->expr)), ret_str, &ret_range);
1149         ret_range = cast_rl(get_type(db_info->expr), ret_range);
1150         if (!ret_range)
1151                 ret_range = alloc_whole_rl(get_type(db_info->expr));
1152
1153         comparison = db_info->comparison;
1154         if (db_info->left)
1155                 comparison = flip_comparison(comparison);
1156
1157         if (db_info->true_side) {
1158                 if (!possibly_true_rl(var_rl, comparison, ret_range))
1159                         return 0;
1160                 if (type == PARAM_LIMIT)
1161                         param_limit_implications(db_info->expr, param, key, value, &db_info->implied);
1162                 else if (type > PARAM_LIMIT)
1163                         set_implied_states(db_info);
1164                 filter_by_comparison(&var_rl, comparison, ret_range);
1165                 filter_by_comparison(&ret_range, flip_comparison(comparison), var_rl);
1166         } else {
1167                 if (!possibly_false_rl(var_rl, comparison, ret_range))
1168                         return 0;
1169                 if (type == PARAM_LIMIT)
1170                         param_limit_implications(db_info->expr, param, key, value, &db_info->implied);
1171                 else if (type > PARAM_LIMIT)
1172                         set_implied_states(db_info);
1173                 filter_by_comparison(&var_rl, negate_comparison(comparison), ret_range);
1174                 filter_by_comparison(&ret_range, flip_comparison(negate_comparison(comparison)), var_rl);
1175         }
1176
1177         handle_ret_equals_param(ret_str, ret_range, db_info->expr);
1178
1179         if (type == INTERNAL) {
1180                 set_state(-1, "unnull_path", NULL, &true_state);
1181                 call_string_hooks(return_string_hooks, db_info->expr, ret_str);
1182                 store_return_state(db_info, ret_str, alloc_estate_rl(clone_rl(var_rl)));
1183         }
1184
1185         FOR_EACH_PTR(db_info->callbacks, tmp) {
1186                 if (tmp->type == type)
1187                         call_db_return_callback(db_info, tmp, param, key, value);
1188         } END_FOR_EACH_PTR(tmp);
1189
1190         fake_return_assignment(db_info, type, param, key, value);
1191
1192         return 0;
1193 }
1194
1195 static void compare_db_return_states_callbacks(struct expression *left, int comparison, struct expression *right, struct stree *implied_true, struct stree *implied_false)
1196 {
1197         struct stree *orig_states;
1198         struct stree *true_states;
1199         struct stree *false_states;
1200         struct sm_state *sm;
1201         struct db_callback_info db_info = {};
1202         struct expression *var_expr;
1203         struct expression *call_expr;
1204         struct range_list *rl;
1205         int call_on_left;
1206
1207         orig_states = clone_stree(__get_cur_stree());
1208
1209         /* legacy cruft.  need to fix call_implies_callbacks(). */
1210         call_on_left = 1;
1211         call_expr = left;
1212         var_expr = right;
1213         if (left->type != EXPR_CALL) {
1214                 call_on_left = 0;
1215                 call_expr = right;
1216                 var_expr = left;
1217         }
1218
1219         get_absolute_rl(var_expr, &rl);
1220
1221         db_info.comparison = comparison;
1222         db_info.expr = call_expr;
1223         db_info.rl = rl;
1224         db_info.left = call_on_left;
1225         db_info.callbacks = db_return_states_list;
1226         db_info.var_expr = var_expr;
1227
1228         call_void_fns(return_states_before);
1229
1230         db_info.true_side = 1;
1231         db_info.stree = NULL;
1232         db_info.prev_return_id = -1;
1233         __push_fake_cur_stree();
1234         sql_select_return_states("return_id, return, type, parameter, key, value",
1235                                  call_expr, db_compare_callback, &db_info);
1236         set_other_side_state(&db_info);
1237         process_return_states(&db_info);
1238         true_states = db_info.stree;
1239         if (!true_states && db_info.has_states) {
1240                 __push_fake_cur_stree();
1241                 set_path_impossible();
1242                 true_states = __pop_fake_cur_stree();
1243         }
1244
1245         nullify_path();
1246         __unnullify_path();
1247         FOR_EACH_SM(orig_states, sm) {
1248                 __set_sm_cur_stree(sm);
1249         } END_FOR_EACH_SM(sm);
1250
1251         db_info.true_side = 0;
1252         db_info.stree = NULL;
1253         db_info.prev_return_id = -1;
1254         db_info.cull = 0;
1255         __push_fake_cur_stree();
1256         sql_select_return_states("return_id, return, type, parameter, key, value", call_expr,
1257                         db_compare_callback, &db_info);
1258         set_other_side_state(&db_info);
1259         process_return_states(&db_info);
1260         false_states = db_info.stree;
1261         if (!false_states && db_info.has_states) {
1262                 __push_fake_cur_stree();
1263                 set_path_impossible();
1264                 false_states = __pop_fake_cur_stree();
1265         }
1266
1267         nullify_path();
1268         __unnullify_path();
1269         FOR_EACH_SM(orig_states, sm) {
1270                 __set_sm_cur_stree(sm);
1271         } END_FOR_EACH_SM(sm);
1272
1273         free_stree(&orig_states);
1274
1275         FOR_EACH_SM(true_states, sm) {
1276                 __set_true_false_sm(sm, NULL);
1277         } END_FOR_EACH_SM(sm);
1278         FOR_EACH_SM(false_states, sm) {
1279                 __set_true_false_sm(NULL, sm);
1280         } END_FOR_EACH_SM(sm);
1281
1282         free_stree(&true_states);
1283         free_stree(&false_states);
1284
1285         call_return_states_after_hooks(call_expr);
1286
1287         FOR_EACH_SM(implied_true, sm) {
1288                 __set_true_false_sm(sm, NULL);
1289         } END_FOR_EACH_SM(sm);
1290         FOR_EACH_SM(implied_false, sm) {
1291                 __set_true_false_sm(NULL, sm);
1292         } END_FOR_EACH_SM(sm);
1293 }
1294
1295 void function_comparison(struct expression *left, int comparison, struct expression *right)
1296 {
1297         struct expression *var_expr;
1298         struct expression *call_expr;
1299         struct stree *implied_true = NULL;
1300         struct stree *implied_false = NULL;
1301         struct range_list *rl;
1302         sval_t sval;
1303         int call_on_left;
1304
1305         // TODO: faked_assign delete this
1306         // condition calls should be faked and then handled as assignments
1307         // this code is a lazy work around
1308
1309         if (unreachable())
1310                 return;
1311
1312         /* legacy cruft.  need to fix call_implies_callbacks(). */
1313         call_on_left = 1;
1314         call_expr = left;
1315         var_expr = right;
1316         if (left->type != EXPR_CALL) {
1317                 call_on_left = 0;
1318                 call_expr = right;
1319                 var_expr = left;
1320         }
1321
1322         get_absolute_rl(var_expr, &rl);
1323
1324         if (rl_to_sval(rl, &sval))
1325                 call_implies_callbacks(comparison, call_expr, sval, call_on_left, &implied_true, &implied_false);
1326
1327         compare_db_return_states_callbacks(left, comparison, right, implied_true, implied_false);
1328         free_stree(&implied_true);
1329         free_stree(&implied_false);
1330 }
1331
1332 static void call_ranged_return_hooks(struct db_callback_info *db_info)
1333 {
1334         struct call_back_list *call_backs;
1335         struct range_list *range_rl;
1336         struct expression *expr;
1337         struct fcall_back *tmp;
1338         const char *fn_name;
1339
1340         expr = strip_expr(db_info->expr);
1341         while (expr->type == EXPR_ASSIGNMENT)
1342                 expr = strip_expr(expr->right);
1343         if (expr->type != EXPR_CALL)
1344                 return;
1345
1346         fn_name = get_fn_name(expr->fn);
1347         call_backs = get_call_backs(fn_name);
1348         FOR_EACH_PTR(call_backs, tmp) {
1349                 if (tmp->type != RANGED_CALL)
1350                         continue;
1351                 range_rl = alloc_rl(tmp->range->min, tmp->range->max);
1352                 range_rl = cast_rl(estate_type(db_info->ret_state), range_rl);
1353                 if (possibly_true_rl(range_rl, SPECIAL_EQUAL, estate_rl(db_info->ret_state)))
1354                         (tmp->u.ranged)(fn_name, expr, db_info->expr, tmp->info);
1355         } END_FOR_EACH_PTR(tmp);
1356
1357         FOR_EACH_PTR(call_backs, tmp) {
1358                 if (tmp->type != RANGED_EXACT)
1359                         continue;
1360                 if (!estate_rl(db_info->ret_state))
1361                         continue;
1362
1363                 range_rl = alloc_rl(tmp->range->min, tmp->range->max);
1364                 range_rl = cast_rl(estate_type(db_info->ret_state), range_rl);
1365
1366                 /*
1367                  * If there is an returned value out of range then this is not
1368                  * an exact match.  In other words, "0,4096-ptr_max" is not
1369                  * necessarily a valid match.
1370                  *
1371                  */
1372                 if (remove_range(estate_rl(db_info->ret_state),
1373                                  rl_min(range_rl), rl_max(range_rl)))
1374                         continue;
1375                 (tmp->u.ranged)(fn_name, expr, db_info->expr, tmp->info);
1376         } END_FOR_EACH_PTR(tmp);
1377 }
1378
1379 static int db_assign_return_states_callback(void *_info, int argc, char **argv, char **azColName)
1380 {
1381         struct db_callback_info *db_info = _info;
1382         struct range_list *ret_range;
1383         int type, param;
1384         char *ret_str, *key, *value;
1385         struct return_implies_callback *tmp;
1386         int return_id;
1387
1388         if (argc != 6)
1389                 return 0;
1390
1391         return_id = atoi(argv[0]);
1392         ret_str = argv[1];
1393         type = atoi(argv[2]);
1394         param = atoi(argv[3]);
1395         key = argv[4];
1396         value = argv[5];
1397
1398         if (db_info->prev_return_id != -1 && type == INTERNAL) {
1399                 call_ranged_return_hooks(db_info);
1400                 set_return_assign_state(db_info);
1401                 process_return_states(db_info);
1402                 __push_fake_cur_stree();
1403                 db_info->cull = 0;
1404         }
1405         db_info->prev_return_id = return_id;
1406
1407         if (type == INTERNAL && func_type_mismatch(db_info->expr, value))
1408                 db_info->cull = 1;
1409         if (db_info->cull)
1410                 return 0;
1411         if (type == CULL_PATH) {
1412                 db_info->cull = 1;
1413                 return 0;
1414         }
1415         if (is_impossible_data(type, db_info, param, key, value)) {
1416                 db_info->cull = 1;
1417                 return 0;
1418         }
1419
1420         if (type == PARAM_LIMIT)
1421                 param_limit_implications(db_info->expr, param, key, value, &db_info->implied);
1422         else if (type > PARAM_LIMIT)
1423                 set_implied_states(db_info);
1424
1425         db_info->handled = 1;
1426         call_results_to_rl(db_info->expr->right, get_type(strip_expr(db_info->expr->right)), ret_str, &ret_range);
1427         if (!ret_range)
1428                 ret_range = alloc_whole_rl(get_type(strip_expr(db_info->expr->right)));
1429         ret_range = cast_rl(get_type(db_info->expr->right), ret_range);
1430
1431         if (type == INTERNAL) {
1432                 set_state(-1, "unnull_path", NULL, &true_state);
1433                 __add_comparison_info(db_info->expr->left, strip_expr(db_info->expr->right), ret_str);
1434                 call_string_hooks(return_string_hooks, db_info->expr, ret_str);
1435                 store_return_state(db_info, ret_str, alloc_estate_rl(ret_range));
1436         }
1437
1438         FOR_EACH_PTR(db_return_states_list, tmp) {
1439                 if (tmp->type == type)
1440                         call_db_return_callback(db_info, tmp, param, key, value);
1441         } END_FOR_EACH_PTR(tmp);
1442
1443         fake_return_assignment(db_info, type, param, key, value);
1444
1445         return 0;
1446 }
1447
1448 static int db_return_states_assign(struct expression *expr)
1449 {
1450         struct expression *right;
1451         struct sm_state *sm;
1452         struct db_callback_info db_info = {};
1453
1454         right = strip_expr(expr->right);
1455
1456         db_info.prev_return_id = -1;
1457         db_info.expr = expr;
1458         db_info.stree = NULL;
1459         db_info.handled = 0;
1460
1461         call_void_fns(return_states_before);
1462
1463         __push_fake_cur_stree();
1464         sql_select_return_states("return_id, return, type, parameter, key, value",
1465                         right, db_assign_return_states_callback, &db_info);
1466         if (option_debug) {
1467                 sm_msg("%s return_id %d return_ranges %s",
1468                         db_info.cull ? "culled" : "merging",
1469                         db_info.prev_return_id,
1470                         db_info.ret_state ? db_info.ret_state->name : "'<empty>'");
1471         }
1472         if (db_info.handled)
1473                 call_ranged_return_hooks(&db_info);
1474         set_return_assign_state(&db_info);
1475         process_return_states(&db_info);
1476
1477         if (!db_info.stree && db_info.cull) { /* this means we culled everything */
1478                 set_extra_expr_mod(expr->left, alloc_estate_whole(get_type(expr->left)));
1479                 set_path_impossible();
1480         }
1481         FOR_EACH_SM(db_info.stree, sm) {
1482                 __set_sm(sm);
1483         } END_FOR_EACH_SM(sm);
1484
1485         free_stree(&db_info.stree);
1486         call_return_states_after_hooks(right);
1487
1488         return db_info.handled;
1489 }
1490
1491 static bool handle_implied_return(struct expression *expr)
1492 {
1493         struct range_list *rl;
1494
1495         if (!get_implied_return(expr->right, &rl))
1496                 return false;
1497         rl = cast_rl(get_type(expr->left), rl);
1498         set_extra_expr_mod(expr->left, alloc_estate_rl(rl));
1499         return true;
1500 }
1501
1502 static void match_assign_call(struct expression *expr)
1503 {
1504         struct call_back_list *call_backs;
1505         const char *fn_name;
1506         struct expression *right;
1507         int handled = 0;
1508         struct range_list *rl;
1509
1510         if (expr->op != '=')
1511                 return;
1512
1513         right = strip_expr(expr->right);
1514         if (is_fake_call(right))
1515                 return;
1516
1517         fn_name = get_fn_name(right->fn);
1518         call_backs = get_call_backs(fn_name);
1519
1520         /*
1521          * The ordering here is sort of important.
1522          * One example, of how this matters is that when we do:
1523          *
1524          *      len = strlen(str);
1525          *
1526          * That is handled by smatch_common_functions.c and smatch_strlen.c.
1527          * They use implied_return and function_assign_hook respectively.
1528          * We want to get the implied return first before we do the function
1529          * assignment hook otherwise we end up writing the wrong thing for len
1530          * in smatch_extra.c because we assume that it already holds the
1531          * strlen() when we haven't set it yet.
1532          */
1533
1534         if (db_return_states_assign(expr))
1535                 handled = 1;
1536         else
1537                 handled = assign_ranged_funcs(fn_name, expr, call_backs);
1538         handled |= handle_implied_return(expr);
1539
1540
1541         call_call_backs(call_backs, ASSIGN_CALL, fn_name, expr);
1542
1543         if (handled)
1544                 return;
1545
1546         /* assignment wasn't handled at all */
1547         get_absolute_rl(expr->right, &rl);
1548         rl = cast_rl(get_type(expr->left), rl);
1549         set_extra_expr_mod(expr->left, alloc_estate_rl(rl));
1550 }
1551
1552 static int db_return_states_callback(void *_info, int argc, char **argv, char **azColName)
1553 {
1554         struct db_callback_info *db_info = _info;
1555         struct range_list *ret_range;
1556         int type, param;
1557         char *ret_str, *key, *value;
1558         struct return_implies_callback *tmp;
1559         int return_id;
1560
1561         if (argc != 6)
1562                 return 0;
1563
1564         return_id = atoi(argv[0]);
1565         ret_str = argv[1];
1566         type = atoi(argv[2]);
1567         param = atoi(argv[3]);
1568         key = argv[4];
1569         value = argv[5];
1570
1571         if (db_info->prev_return_id != -1 && type == INTERNAL) {
1572                 call_ranged_return_hooks(db_info);
1573                 process_return_states(db_info);
1574                 __push_fake_cur_stree();
1575                 __unnullify_path();
1576                 db_info->cull = 0;
1577         }
1578         db_info->prev_return_id = return_id;
1579
1580         if (type == INTERNAL && func_type_mismatch(db_info->expr, value))
1581                 db_info->cull = 1;
1582         if (db_info->cull)
1583                 return 0;
1584         if (type == CULL_PATH) {
1585                 db_info->cull = 1;
1586                 return 0;
1587         }
1588         if (is_impossible_data(type, db_info, param, key, value)) {
1589                 db_info->cull = 1;
1590                 return 0;
1591         }
1592
1593         if (type == PARAM_LIMIT)
1594                 param_limit_implications(db_info->expr, param, key, value, &db_info->implied);
1595         else if (type > PARAM_LIMIT)
1596                 set_implied_states(db_info);
1597
1598         call_results_to_rl(db_info->expr, get_type(strip_expr(db_info->expr)), ret_str, &ret_range);
1599         ret_range = cast_rl(get_type(db_info->expr), ret_range);
1600
1601         if (type == INTERNAL) {
1602                 struct smatch_state *state;
1603
1604                 set_state(-1, "unnull_path", NULL, &true_state);
1605                 call_string_hooks(return_string_hooks, db_info->expr, ret_str);
1606                 state = alloc_estate_rl(ret_range);
1607                 store_return_state(db_info, ret_str, state);
1608         }
1609
1610         FOR_EACH_PTR(db_return_states_list, tmp) {
1611                 if (tmp->type == type)
1612                         call_db_return_callback(db_info, tmp, param, key, value);
1613         } END_FOR_EACH_PTR(tmp);
1614
1615         fake_return_assignment(db_info, type, param, key, value);
1616
1617         return 0;
1618 }
1619
1620 static void db_return_states(struct expression *expr)
1621 {
1622         struct sm_state *sm;
1623         struct db_callback_info db_info = {};
1624
1625         if (!__get_cur_stree())  /* no return functions */
1626                 return;
1627
1628         db_info.prev_return_id = -1;
1629         db_info.expr = expr;
1630         db_info.stree = NULL;
1631
1632         call_void_fns(return_states_before);
1633
1634         __push_fake_cur_stree();
1635         __unnullify_path();
1636         sql_select_return_states("return_id, return, type, parameter, key, value",
1637                         expr, db_return_states_callback, &db_info);
1638         call_ranged_return_hooks(&db_info);
1639         process_return_states(&db_info);
1640
1641         FOR_EACH_SM(db_info.stree, sm) {
1642                 __set_sm(sm);
1643         } END_FOR_EACH_SM(sm);
1644
1645         free_stree(&db_info.stree);
1646         call_return_states_after_hooks(expr);
1647 }
1648
1649 static void db_return_states_call(struct expression *expr)
1650 {
1651         if (unreachable())
1652                 return;
1653
1654         if (is_assigned_call(expr) || is_fake_assigned_call(expr))
1655                 return;
1656         if (is_condition_call(expr))
1657                 return;
1658         db_return_states(expr);
1659 }
1660
1661 static void match_function_call_early(struct expression *expr)
1662 {
1663         call_function_hooks(expr, REGULAR_CALL_EARLY);
1664 }
1665
1666 static void match_function_call(struct expression *expr)
1667 {
1668         call_function_hooks(expr, REGULAR_CALL);
1669         db_return_states_call(expr);
1670 }
1671
1672 static void match_macro_assign(struct expression *expr)
1673 {
1674         struct call_back_list *call_backs;
1675         const char *macro;
1676         struct expression *right;
1677
1678         right = strip_expr(expr->right);
1679         macro = get_macro_name(right->pos);
1680         call_backs = search_callback(func_hash, (char *)macro);
1681         if (!call_backs)
1682                 return;
1683         call_call_backs(call_backs, MACRO_ASSIGN, macro, expr);
1684         call_call_backs(call_backs, MACRO_ASSIGN_EXTRA, macro, expr);
1685 }
1686
1687 bool get_implied_return(struct expression *expr, struct range_list **rl)
1688 {
1689         struct call_back_list *call_backs;
1690         struct fcall_back *tmp;
1691         bool handled = false;
1692         char *fn;
1693
1694         *rl = NULL;
1695
1696         expr = strip_expr(expr);
1697         fn = expr_to_var(expr->fn);
1698         if (!fn)
1699                 goto out;
1700
1701         call_backs = search_callback(func_hash, fn);
1702
1703         FOR_EACH_PTR(call_backs, tmp) {
1704                 if (tmp->type == IMPLIED_RETURN)
1705                         handled |= (tmp->u.implied_return)(expr, tmp->info, rl);
1706         } END_FOR_EACH_PTR(tmp);
1707
1708 out:
1709         free_string(fn);
1710         return handled;
1711 }
1712
1713 struct range_list *get_range_implications(const char *fn)
1714 {
1715         struct call_back_list *call_backs;
1716         struct range_list *ret = NULL;
1717         struct fcall_back *tmp;
1718
1719         call_backs = search_callback(func_hash, (char *)fn);
1720
1721         FOR_EACH_PTR(call_backs, tmp) {
1722                 if (tmp->type != RANGED_CALL &&
1723                     tmp->type != RANGED_EXACT)
1724                         continue;
1725                 add_ptr_list(&ret, tmp->range);
1726         } END_FOR_EACH_PTR(tmp);
1727
1728         return ret;
1729 }
1730
1731 void create_function_hook_hash(void)
1732 {
1733         func_hash = create_function_hashtable(5000);
1734 }
1735
1736 void register_function_hooks_early(int id)
1737 {
1738         add_hook(&match_function_call_early, FUNCTION_CALL_HOOK_BEFORE);
1739 }
1740
1741 void register_function_hooks(int id)
1742 {
1743         add_hook(&match_function_call, CALL_HOOK_AFTER_INLINE);
1744         add_hook(&match_assign_call, CALL_ASSIGNMENT_HOOK);
1745         add_hook(&match_macro_assign, MACRO_ASSIGNMENT_HOOK);
1746 }