extra: handle "if (a - 3 > 100) "
[smatch.git] / smatch_function_hooks.c
blobd297007ff11230f9bf7c766232b29753e0782c31
1 /*
2 * sparse/smatch_function_hooks.c
4 * Copyright (C) 2009 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
8 */
11 * There are several types of function hooks:
12 * add_function_hook() - For any time a function is called.
13 * add_function_assign_hook() - foo = the_function().
14 * add_implied_return_hook() - Calculates the implied return value.
15 * add_macro_assign_hook() - foo = the_macro().
16 * return_implies_state() - For when a return value of 1 implies locked
17 * and 0 implies unlocked. etc. etc.
21 #include <stdlib.h>
22 #include <stdio.h>
23 #include "smatch.h"
24 #include "smatch_slist.h"
25 #include "smatch_extra.h"
26 #include "smatch_function_hashtable.h"
28 struct fcall_back {
29 int type;
30 struct data_range *range;
31 union {
32 func_hook *call_back;
33 implication_hook *ranged;
34 implied_return_hook *implied_return;
35 } u;
36 void *info;
39 ALLOCATOR(fcall_back, "call backs");
40 DECLARE_PTR_LIST(call_back_list, struct fcall_back);
42 DEFINE_FUNCTION_HASHTABLE_STATIC(callback, struct fcall_back, struct call_back_list);
43 static struct hashtable *func_hash;
45 #define REGULAR_CALL 0
46 #define RANGED_CALL 1
47 #define ASSIGN_CALL 2
48 #define IMPLIED_RETURN 3
49 #define MACRO_ASSIGN 4
50 #define MACRO_ASSIGN_EXTRA 5
52 struct return_implies_callback {
53 int type;
54 return_implies_hook *callback;
56 ALLOCATOR(return_implies_callback, "return_implies callbacks");
57 DECLARE_PTR_LIST(db_implies_list, struct return_implies_callback);
58 static struct db_implies_list *db_return_states_list;
60 typedef void (void_fn)(void);
61 DECLARE_PTR_LIST(void_fn_list, void_fn *);
62 static struct void_fn_list *return_states_before;
63 static struct void_fn_list *return_states_after;
65 static struct fcall_back *alloc_fcall_back(int type, void *call_back,
66 void *info)
68 struct fcall_back *cb;
70 cb = __alloc_fcall_back(0);
71 cb->type = type;
72 cb->u.call_back = call_back;
73 cb->info = info;
74 return cb;
77 void add_function_hook(const char *look_for, func_hook *call_back, void *info)
79 struct fcall_back *cb;
81 cb = alloc_fcall_back(REGULAR_CALL, call_back, info);
82 add_callback(func_hash, look_for, cb);
85 void add_function_assign_hook(const char *look_for, func_hook *call_back,
86 void *info)
88 struct fcall_back *cb;
90 cb = alloc_fcall_back(ASSIGN_CALL, call_back, info);
91 add_callback(func_hash, look_for, cb);
94 void add_implied_return_hook(const char *look_for,
95 implied_return_hook *call_back,
96 void *info)
98 struct fcall_back *cb;
100 cb = alloc_fcall_back(IMPLIED_RETURN, call_back, info);
101 add_callback(func_hash, look_for, cb);
104 void add_macro_assign_hook(const char *look_for, func_hook *call_back,
105 void *info)
107 struct fcall_back *cb;
109 cb = alloc_fcall_back(MACRO_ASSIGN, call_back, info);
110 add_callback(func_hash, look_for, cb);
113 void add_macro_assign_hook_extra(const char *look_for, func_hook *call_back,
114 void *info)
116 struct fcall_back *cb;
118 cb = alloc_fcall_back(MACRO_ASSIGN_EXTRA, call_back, info);
119 add_callback(func_hash, look_for, cb);
122 void return_implies_state(const char *look_for, long long start, long long end,
123 implication_hook *call_back, void *info)
125 struct fcall_back *cb;
127 cb = alloc_fcall_back(RANGED_CALL, call_back, info);
128 cb->range = alloc_range_perm(ll_to_sval(start), ll_to_sval(end));
129 add_callback(func_hash, look_for, cb);
132 void add_db_return_states_callback(int type, return_implies_hook *callback)
134 struct return_implies_callback *cb = __alloc_return_implies_callback(0);
136 cb->type = type;
137 cb->callback = callback;
138 add_ptr_list(&db_return_states_list, cb);
141 void add_db_return_states_before(void_fn *fn)
143 void_fn **p = malloc(sizeof(void_fn *));
144 *p = fn;
145 add_ptr_list(&return_states_before, p);
148 void add_db_return_states_after(void_fn *fn)
150 void_fn **p = malloc(sizeof(void_fn *));
151 *p = fn;
152 add_ptr_list(&return_states_after, p);
155 static void call_return_states_before_hooks(void)
157 void_fn **fn;
159 FOR_EACH_PTR(return_states_before, fn) {
160 (*fn)();
161 } END_FOR_EACH_PTR(fn);
164 static void call_return_states_after_hooks(void)
166 void_fn **fn;
168 FOR_EACH_PTR(return_states_after, fn) {
169 (*fn)();
170 } END_FOR_EACH_PTR(fn);
173 static int call_call_backs(struct call_back_list *list, int type,
174 const char *fn, struct expression *expr)
176 struct fcall_back *tmp;
177 int handled = 0;
179 FOR_EACH_PTR(list, tmp) {
180 if (tmp->type == type) {
181 (tmp->u.call_back)(fn, expr, tmp->info);
182 handled = 1;
184 } END_FOR_EACH_PTR(tmp);
186 return handled;
189 static void call_ranged_call_backs(struct call_back_list *list,
190 const char *fn, struct expression *call_expr,
191 struct expression *assign_expr)
193 struct fcall_back *tmp;
195 FOR_EACH_PTR(list, tmp) {
196 (tmp->u.ranged)(fn, call_expr, assign_expr, tmp->info);
197 } END_FOR_EACH_PTR(tmp);
200 static struct call_back_list *get_same_ranged_call_backs(struct call_back_list *list,
201 struct data_range *drange)
203 struct call_back_list *ret = NULL;
204 struct fcall_back *tmp;
206 FOR_EACH_PTR(list, tmp) {
207 if (tmp->type != RANGED_CALL)
208 continue;
209 if (ranges_equiv(tmp->range, drange))
210 add_ptr_list(&ret, tmp);
211 } END_FOR_EACH_PTR(tmp);
212 return ret;
215 static int in_list_exact_sval(struct range_list *list, struct data_range *drange)
217 struct data_range *tmp;
219 FOR_EACH_PTR(list, tmp) {
220 if (ranges_equiv(tmp, drange))
221 return 1;
222 } END_FOR_EACH_PTR(tmp);
223 return 0;
226 static int assign_ranged_funcs(const char *fn, struct expression *expr,
227 struct call_back_list *call_backs)
229 struct fcall_back *tmp;
230 struct sm_state *sm;
231 char *var_name;
232 struct symbol *sym;
233 struct smatch_state *estate;
234 struct state_list *tmp_slist;
235 struct state_list *final_states = NULL;
236 struct range_list *handled_ranges = NULL;
237 struct call_back_list *same_range_call_backs = NULL;
238 int handled = 0;
240 if (!call_backs)
241 return 0;
243 var_name = expr_to_var_sym(expr->left, &sym);
244 if (!var_name || !sym)
245 goto free;
247 FOR_EACH_PTR(call_backs, tmp) {
248 if (tmp->type != RANGED_CALL)
249 continue;
251 if (in_list_exact_sval(handled_ranges, tmp->range))
252 continue;
253 __push_fake_cur_slist();
254 tack_on(&handled_ranges, tmp->range);
256 same_range_call_backs = get_same_ranged_call_backs(call_backs, tmp->range);
257 call_ranged_call_backs(same_range_call_backs, fn, expr->right, expr);
258 __free_ptr_list((struct ptr_list **)&same_range_call_backs);
260 estate = alloc_estate_range(tmp->range->min, tmp->range->max);
261 set_extra_mod(var_name, sym, estate);
263 tmp_slist = __pop_fake_cur_slist();
264 merge_slist(&final_states, tmp_slist);
265 free_slist(&tmp_slist);
266 handled = 1;
267 } END_FOR_EACH_PTR(tmp);
269 FOR_EACH_PTR(final_states, sm) {
270 __set_sm(sm);
271 } END_FOR_EACH_PTR(sm);
273 free_slist(&final_states);
274 free:
275 free_string(var_name);
276 return handled;
279 static int call_implies_callbacks(int comparison, struct expression *expr, sval_t sval, int left)
281 struct call_back_list *call_backs;
282 struct fcall_back *tmp;
283 const char *fn;
284 struct data_range *value_range;
285 struct state_list *true_states = NULL;
286 struct state_list *false_states = NULL;
287 struct state_list *tmp_slist;
288 struct sm_state *sm;
290 if (expr->fn->type != EXPR_SYMBOL || !expr->fn->symbol)
291 return 0;
292 fn = expr->fn->symbol->ident->name;
293 call_backs = search_callback(func_hash, (char *)expr->fn->symbol->ident->name);
294 if (!call_backs)
295 return 0;
296 value_range = alloc_range(sval, sval);
298 /* set true states */
299 __push_fake_cur_slist();
300 FOR_EACH_PTR(call_backs, tmp) {
301 if (tmp->type != RANGED_CALL)
302 continue;
303 if (!true_comparison_range_LR(comparison, tmp->range, value_range, left))
304 continue;
305 (tmp->u.ranged)(fn, expr, NULL, tmp->info);
306 } END_FOR_EACH_PTR(tmp);
307 tmp_slist = __pop_fake_cur_slist();
308 merge_slist(&true_states, tmp_slist);
309 free_slist(&tmp_slist);
311 /* set false states */
312 __push_fake_cur_slist();
313 FOR_EACH_PTR(call_backs, tmp) {
314 if (tmp->type != RANGED_CALL)
315 continue;
316 if (!false_comparison_range_LR(comparison, tmp->range, value_range, left))
317 continue;
318 (tmp->u.ranged)(fn, expr, NULL, tmp->info);
319 } END_FOR_EACH_PTR(tmp);
320 tmp_slist = __pop_fake_cur_slist();
321 merge_slist(&false_states, tmp_slist);
322 free_slist(&tmp_slist);
324 FOR_EACH_PTR(true_states, sm) {
325 __set_true_false_sm(sm, NULL);
326 } END_FOR_EACH_PTR(sm);
327 FOR_EACH_PTR(false_states, sm) {
328 __set_true_false_sm(NULL, sm);
329 } END_FOR_EACH_PTR(sm);
331 free_slist(&true_states);
332 free_slist(&false_states);
333 return 1;
336 struct db_callback_info {
337 int true_side;
338 int comparison;
339 struct expression *expr;
340 struct range_list *rl;
341 int left;
342 struct state_list *slist;
343 struct db_implies_list *callbacks;
345 static struct db_callback_info db_info;
346 static int db_compare_callback(void *unused, int argc, char **argv, char **azColName)
348 struct range_list *ret_range;
349 int type, param;
350 char *key, *value;
351 struct return_implies_callback *tmp;
353 if (argc != 5)
354 return 0;
356 str_to_rl(get_type(strip_expr(db_info.expr)), argv[0], &ret_range);
357 ret_range = cast_rl(get_type(db_info.expr), ret_range);
358 type = atoi(argv[1]);
359 param = atoi(argv[2]);
360 key = argv[3];
361 value = argv[4];
363 if (db_info.true_side) {
364 if (!possibly_true_rl_LR(db_info.comparison,
365 ret_range, db_info.rl,
366 db_info.left))
367 return 0;
368 } else {
369 if (!possibly_false_rl_LR(db_info.comparison,
370 ret_range, db_info.rl,
371 db_info.left))
372 return 0;
375 FOR_EACH_PTR(db_info.callbacks, tmp) {
376 if (tmp->type == type)
377 tmp->callback(db_info.expr, param, key, value);
378 } END_FOR_EACH_PTR(tmp);
379 return 0;
382 void compare_db_return_states_callbacks(int comparison, struct expression *expr, sval_t sval, int left)
384 struct state_list *true_states;
385 struct state_list *false_states;
386 struct sm_state *sm;
388 if (expr->fn->type != EXPR_SYMBOL || !expr->fn->symbol)
389 return;
391 db_info.comparison = comparison;
392 db_info.expr = expr;
393 db_info.rl = alloc_rl(sval, sval);
394 db_info.left = left;
395 db_info.callbacks = db_return_states_list;
397 call_return_states_before_hooks();
399 db_info.true_side = 1;
400 __push_fake_cur_slist();
401 sql_select_return_states("return, type, parameter, key, value", expr,
402 db_compare_callback);
403 true_states = __pop_fake_cur_slist();
405 db_info.true_side = 0;
406 __push_fake_cur_slist();
407 sql_select_return_states("return, type, parameter, key, value", expr,
408 db_compare_callback);
409 false_states = __pop_fake_cur_slist();
411 FOR_EACH_PTR(true_states, sm) {
412 __set_true_false_sm(sm, NULL);
413 } END_FOR_EACH_PTR(sm);
414 FOR_EACH_PTR(false_states, sm) {
415 __set_true_false_sm(NULL, sm);
416 } END_FOR_EACH_PTR(sm);
418 call_return_states_after_hooks();
420 free_slist(&true_states);
421 free_slist(&false_states);
426 void function_comparison(int comparison, struct expression *expr, sval_t sval, int left)
428 if (call_implies_callbacks(comparison, expr, sval, left))
429 return;
430 compare_db_return_states_callbacks(comparison, expr, sval, left);
433 static int prev_return_id;
434 static int db_assign_return_states_callback(void *unused, int argc, char **argv, char **azColName)
436 struct range_list *ret_range;
437 int type, param;
438 char *key, *value;
439 struct return_implies_callback *tmp;
440 struct state_list *slist;
441 int return_id;
443 if (argc != 6)
444 return 0;
446 return_id = atoi(argv[0]);
447 str_to_rl(get_type(strip_expr(db_info.expr->right)), argv[1], &ret_range);
448 if (!ret_range)
449 ret_range = alloc_whole_rl(get_type(strip_expr(db_info.expr->right)));
450 ret_range = cast_rl(get_type(db_info.expr->right), ret_range);
451 type = atoi(argv[2]);
452 param = atoi(argv[3]);
453 key = argv[4];
454 value = argv[5];
456 if (prev_return_id != -1 && return_id != prev_return_id) {
457 slist = __pop_fake_cur_slist();
458 merge_slist(&db_info.slist, slist);
459 __push_fake_cur_slist();
461 prev_return_id = return_id;
463 FOR_EACH_PTR(db_return_states_list, tmp) {
464 if (tmp->type == type)
465 tmp->callback(db_info.expr, param, key, value);
466 } END_FOR_EACH_PTR(tmp);
467 ret_range = cast_rl(get_type(db_info.expr->left), ret_range);
468 set_extra_expr_mod(db_info.expr->left, alloc_estate_rl(ret_range));
470 return 0;
473 static int db_return_states_assign(struct expression *expr)
475 struct expression *right;
476 struct sm_state *sm;
477 struct state_list *slist;
478 int handled = 0;
480 right = strip_expr(expr->right);
481 if (right->fn->type != EXPR_SYMBOL || !right->fn->symbol)
482 return 0;
484 prev_return_id = -1;
485 db_info.expr = expr;
486 db_info.slist = NULL;
488 call_return_states_before_hooks();
490 __push_fake_cur_slist();
491 sql_select_return_states("return_id, return, type, parameter, key, value",
492 right, db_assign_return_states_callback);
493 slist = __pop_fake_cur_slist();
494 merge_slist(&db_info.slist, slist);
496 FOR_EACH_PTR(db_info.slist, sm) {
497 __set_sm(sm);
498 handled = 1;
499 } END_FOR_EACH_PTR(sm);
501 call_return_states_after_hooks();
503 return handled;
506 static int handle_implied_return(struct expression *expr)
508 struct range_list *rl;
510 if (!get_implied_return(expr->right, &rl))
511 return 0;
512 rl = cast_rl(get_type(expr->left), rl);
513 set_extra_expr_mod(expr->left, alloc_estate_rl(rl));
514 return 1;
517 static void match_assign_call(struct expression *expr)
519 struct call_back_list *call_backs;
520 const char *fn;
521 struct expression *right;
522 int handled = 0;
524 right = strip_expr(expr->right);
525 if (right->fn->type != EXPR_SYMBOL || !right->fn->symbol) {
526 set_extra_expr_mod(expr->left, alloc_estate_whole(get_type(expr->left)));
527 return;
529 fn = right->fn->symbol->ident->name;
532 * some of these conflict (they try to set smatch extra twice), so we
533 * call them in order from least important to most important.
536 call_backs = search_callback(func_hash, (char *)fn);
537 call_call_backs(call_backs, ASSIGN_CALL, fn, expr);
539 handled |= db_return_states_assign(expr);
540 handled |= assign_ranged_funcs(fn, expr, call_backs);
541 handled |= handle_implied_return(expr);
543 if (!handled) {
544 struct range_list *rl;
546 if (!get_implied_rl(expr->right, &rl))
547 rl = alloc_whole_rl(get_type(expr->right));
548 rl = cast_rl(get_type(expr->left), rl);
549 set_extra_expr_mod(expr->left, alloc_estate_rl(rl));
553 static int db_return_states_callback(void *unused, int argc, char **argv, char **azColName)
555 struct range_list *ret_range;
556 int type, param;
557 char *key, *value;
558 struct return_implies_callback *tmp;
559 struct state_list *slist;
560 int return_id;
562 if (argc != 6)
563 return 0;
565 return_id = atoi(argv[0]);
566 str_to_rl(get_type(strip_expr(db_info.expr)), argv[1], &ret_range);
567 ret_range = cast_rl(get_type(db_info.expr), ret_range);
568 type = atoi(argv[2]);
569 param = atoi(argv[3]);
570 key = argv[4];
571 value = argv[5];
573 if (prev_return_id != -1 && return_id != prev_return_id) {
574 slist = __pop_fake_cur_slist();
575 merge_slist(&db_info.slist, slist);
576 __push_fake_cur_slist();
577 __unnullify_path();
579 prev_return_id = return_id;
581 FOR_EACH_PTR(db_return_states_list, tmp) {
582 if (tmp->type == type)
583 tmp->callback(db_info.expr, param, key, value);
584 } END_FOR_EACH_PTR(tmp);
586 return 0;
589 static void db_return_states(struct expression *expr)
591 struct sm_state *sm;
592 struct state_list *slist;
594 if (expr->fn->type != EXPR_SYMBOL || !expr->fn->symbol)
595 return;
596 if (!__get_cur_slist()) /* no return functions */
597 return;
599 prev_return_id = -1;
600 db_info.expr = expr;
601 db_info.slist = NULL;
603 call_return_states_before_hooks();
605 __push_fake_cur_slist();
606 __unnullify_path();
607 sql_select_return_states("return_id, return, type, parameter, key, value",
608 expr, db_return_states_callback);
609 slist = __pop_fake_cur_slist();
610 merge_slist(&db_info.slist, slist);
612 FOR_EACH_PTR(db_info.slist, sm) {
613 __set_sm(sm);
614 } END_FOR_EACH_PTR(sm);
616 call_return_states_after_hooks();
619 static int is_assigned_call(struct expression *expr)
621 struct expression *tmp;
623 FOR_EACH_PTR_REVERSE(big_expression_stack, tmp) {
624 if (tmp->type == EXPR_ASSIGNMENT && strip_expr(tmp->right) == expr)
625 return 1;
626 if (tmp->pos.line < expr->pos.line)
627 return 0;
628 } END_FOR_EACH_PTR_REVERSE(tmp);
629 return 0;
632 static void db_return_states_call(struct expression *expr)
634 if (is_assigned_call(expr))
635 return;
636 db_return_states(expr);
639 static void match_function_call(struct expression *expr)
641 struct call_back_list *call_backs;
643 if (expr->fn->type != EXPR_SYMBOL || !expr->fn->symbol)
644 return;
645 call_backs = search_callback(func_hash, (char *)expr->fn->symbol->ident->name);
646 if (call_backs)
647 call_call_backs(call_backs, REGULAR_CALL,
648 expr->fn->symbol->ident->name, expr);
649 db_return_states_call(expr);
652 static void match_macro_assign(struct expression *expr)
654 struct call_back_list *call_backs;
655 const char *macro;
656 struct expression *right;
658 right = strip_expr(expr->right);
659 macro = get_macro_name(right->pos);
660 call_backs = search_callback(func_hash, (char *)macro);
661 if (!call_backs)
662 return;
663 call_call_backs(call_backs, MACRO_ASSIGN, macro, expr);
664 call_call_backs(call_backs, MACRO_ASSIGN_EXTRA, macro, expr);
667 int get_implied_return(struct expression *expr, struct range_list **rl)
669 struct call_back_list *call_backs;
670 struct fcall_back *tmp;
671 int handled = 0;
672 char *fn;
674 *rl = NULL;
676 expr = strip_expr(expr);
677 fn = expr_to_var(expr->fn);
678 if (!fn)
679 goto out;
681 call_backs = search_callback(func_hash, fn);
683 FOR_EACH_PTR(call_backs, tmp) {
684 if (tmp->type == IMPLIED_RETURN) {
685 (tmp->u.implied_return)(expr, tmp->info, rl);
686 handled = 1;
688 } END_FOR_EACH_PTR(tmp);
690 out:
691 free_string(fn);
692 return handled;
695 void create_function_hook_hash(void)
697 func_hash = create_function_hashtable(5000);
700 void register_function_hooks(int id)
702 add_hook(&match_function_call, CALL_HOOK_AFTER_INLINE);
703 add_hook(&match_assign_call, CALL_ASSIGNMENT_HOOK);
704 add_hook(&match_macro_assign, MACRO_ASSIGNMENT_HOOK);