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