55 * not have a ->pool.
56 * merge_sm_state() sets ->left and ->right. (These are the states which were
57 * merged to form the current state.)
58 * a pool: a pool is an slist that has been merged with another slist.
59 */
60
61 #include <time.h>
62 #include "smatch.h"
63 #include "smatch_slist.h"
64 #include "smatch_extra.h"
65
66 char *implied_debug_msg;
67
68 bool implications_off;
69
70 #define implied_debug 0
71 #define DIMPLIED(msg...) do { if (implied_debug) printf(msg); } while (0)
72
73 bool debug_implied(void)
74 {
75 return implied_debug;
76 }
77
78 /*
79 * tmp_range_list():
80 * It messes things up to free range list allocations. This helper fuction
81 * lets us reuse memory instead of doing new allocations.
82 */
83 static struct range_list *tmp_range_list(struct symbol *type, long long num)
84 {
85 static struct range_list *my_list = NULL;
86 static struct data_range *my_range;
87
88 __free_ptr_list((struct ptr_list **)&my_list);
89 my_range = alloc_range(ll_to_sval(num), ll_to_sval(num));
90 add_ptr_list(&my_list, my_range);
91 return my_list;
92 }
93
94 static void print_debug_tf(struct sm_state *sm, int istrue, int isfalse)
95 {
96 if (!implied_debug && !option_debug)
97 return;
98
99 if (istrue && isfalse) {
100 printf("%s: %d: does not exist.\n", show_sm(sm), sm->line);
101 } else if (istrue) {
102 printf("'%s = %s' from %d is true. %s[stree %d]\n", sm->name, show_state(sm->state),
103 sm->line, sm->merged ? "[merged]" : "[leaf]",
104 get_stree_id(sm->pool));
105 } else if (isfalse) {
106 printf("'%s = %s' from %d is false. %s[stree %d]\n", sm->name, show_state(sm->state),
107 sm->line,
108 sm->merged ? "[merged]" : "[leaf]",
109 get_stree_id(sm->pool));
110 } else {
111 printf("'%s = %s' from %d could be true or false. %s[stree %d]\n", sm->name,
112 show_state(sm->state), sm->line,
113 sm->merged ? "[merged]" : "[leaf]",
114 get_stree_id(sm->pool));
115 }
116 }
117
118 static int create_fake_history(struct sm_state *sm, int comparison, struct range_list *rl)
119 {
120 struct range_list *orig_rl;
121 struct range_list *true_rl, *false_rl;
122 struct stree *true_stree, *false_stree;
123 struct sm_state *true_sm, *false_sm;
124 sval_t sval;
125
126 if (is_merged(sm) || sm->left || sm->right)
127 return 0;
128 if (!rl_to_sval(rl, &sval))
129 return 0;
130 if (!estate_rl(sm->state))
131 return 0;
132
133 orig_rl = cast_rl(rl_type(rl), estate_rl(sm->state));
134 split_comparison_rl(orig_rl, comparison, rl, &true_rl, &false_rl, NULL, NULL);
135
136 true_rl = rl_truncate_cast(estate_type(sm->state), true_rl);
137 false_rl = rl_truncate_cast(estate_type(sm->state), false_rl);
138 if (is_whole_rl(true_rl) || is_whole_rl(false_rl) ||
139 !true_rl || !false_rl ||
140 rl_equiv(orig_rl, true_rl) || rl_equiv(orig_rl, false_rl) ||
141 rl_equiv(estate_rl(sm->state), true_rl) || rl_equiv(estate_rl(sm->state), false_rl))
142 return 0;
143
144 if (rl_intersection(true_rl, false_rl)) {
145 /*
146 * Normally these won't intersect, but one exception is when
147 * we're dealing with mtags. We have a long list of mtags and
148 * then negate the list. Now it's over the limit for mtag list
149 * length and we squash it down to 4096-ptr_max. So then it's
150 * possible for the true and false rl to overlap.
151 */
152 return 0;
153 }
154
155 if (implied_debug)
156 sm_msg("fake_history: %s vs %s. %s %s %s. --> T: %s F: %s",
157 sm->name, show_rl(rl), sm->state->name, show_special(comparison), show_rl(rl),
158 show_rl(true_rl), show_rl(false_rl));
159
160 true_sm = clone_sm(sm);
161 false_sm = clone_sm(sm);
162
163 true_sm->state = clone_partial_estate(sm->state, true_rl);
164 free_slist(&true_sm->possible);
165 add_possible_sm(true_sm, true_sm);
166 false_sm->state = clone_partial_estate(sm->state, false_rl);
167 free_slist(&false_sm->possible);
168 add_possible_sm(false_sm, false_sm);
169
170 true_stree = clone_stree(sm->pool);
171 false_stree = clone_stree(sm->pool);
172
173 overwrite_sm_state_stree(&true_stree, true_sm);
174 overwrite_sm_state_stree(&false_stree, false_sm);
175
176 true_sm->pool = true_stree;
177 false_sm->pool = false_stree;
216 return 1;
217 } END_FOR_EACH_PTR(tmp);
218 return 0;
219 }
220
221 static int remove_pool(struct state_list **pools, struct stree *remove)
222 {
223 struct sm_state *tmp;
224 int ret = 0;
225
226 FOR_EACH_PTR(*pools, tmp) {
227 if (tmp->pool == remove) {
228 DELETE_CURRENT_PTR(tmp);
229 ret = 1;
230 }
231 } END_FOR_EACH_PTR(tmp);
232
233 return ret;
234 }
235
236 /*
237 * If 'foo' == 99 add it that pool to the true pools. If it's false, add it to
238 * the false pools. If we're not sure, then we don't add it to either.
239 */
240 static void do_compare(struct sm_state *sm, int comparison, struct range_list *rl,
241 struct state_list **true_stack,
242 struct state_list **maybe_stack,
243 struct state_list **false_stack,
244 int *mixed, struct sm_state *gate_sm)
245 {
246 int istrue;
247 int isfalse;
248 struct range_list *var_rl;
249
250 if (!sm->pool)
251 return;
252
253 var_rl = cast_rl(rl_type(rl), estate_rl(sm->state));
254
255 istrue = !possibly_false_rl(var_rl, comparison, rl);
256 isfalse = !possibly_true_rl(var_rl, comparison, rl);
257
258 print_debug_tf(sm, istrue, isfalse);
259
260 /* give up if we have borrowed implications (smatch_equiv.c) */
261 if (sm->sym != gate_sm->sym ||
262 strcmp(sm->name, gate_sm->name) != 0) {
263 if (mixed)
264 *mixed = 1;
265 }
266
267 if (mixed && !*mixed && !is_merged(sm) && !istrue && !isfalse) {
268 if (!create_fake_history(sm, comparison, rl))
269 *mixed = 1;
270 }
271
272 if (istrue)
273 add_pool(true_stack, sm);
274 else if (isfalse)
275 add_pool(false_stack, sm);
276 else
298 */
299 static void __separate_pools(struct sm_state *sm, int comparison, struct range_list *rl,
300 struct state_list **true_stack,
301 struct state_list **maybe_stack,
302 struct state_list **false_stack,
303 struct state_list **checked, int *mixed, struct sm_state *gate_sm,
304 struct timeval *start_time)
305 {
306 int free_checked = 0;
307 struct state_list *checked_states = NULL;
308 struct timeval now, diff;
309
310 if (!sm)
311 return;
312
313 gettimeofday(&now, NULL);
314 timersub(&now, start_time, &diff);
315 if (diff.tv_sec >= 1) {
316 if (implied_debug) {
317 sm_msg("debug: %s: implications taking too long. (%s %s %s)",
318 __func__, sm->state->name, show_special(comparison), show_rl(rl));
319 }
320 if (mixed)
321 *mixed = 1;
322 }
323
324 if (checked == NULL) {
325 checked = &checked_states;
326 free_checked = 1;
327 }
328 if (is_checked(*checked, sm))
329 return;
330 add_ptr_list(checked, sm);
331
332 do_compare(sm, comparison, rl, true_stack, maybe_stack, false_stack, mixed, gate_sm);
333
334 __separate_pools(sm->left, comparison, rl, true_stack, maybe_stack, false_stack, checked, mixed, gate_sm, start_time);
335 __separate_pools(sm->right, comparison, rl, true_stack, maybe_stack, false_stack, checked, mixed, gate_sm, start_time);
336 if (free_checked)
337 free_slist(checked);
338 }
576 avl_insert(&ret, filtered_sm);
577 } END_FOR_EACH_SM(tmp);
578 return ret;
579 }
580
581 static void separate_and_filter(struct sm_state *sm, int comparison, struct range_list *rl,
582 struct stree *pre_stree,
583 struct stree **true_states,
584 struct stree **false_states,
585 int *mixed)
586 {
587 struct state_list *true_stack = NULL;
588 struct state_list *false_stack = NULL;
589 struct timeval time_before;
590 struct timeval time_after;
591 int sec;
592
593 gettimeofday(&time_before, NULL);
594
595 DIMPLIED("checking implications: (%s (%s) %s %s)\n",
596 sm->name, sm->state->name, show_special(comparison), show_rl(rl));
597
598 if (!is_merged(sm)) {
599 DIMPLIED("%d '%s' from line %d is not merged.\n", get_lineno(), sm->name, sm->line);
600 return;
601 }
602
603 separate_pools(sm, comparison, rl, &true_stack, &false_stack, NULL, mixed);
604
605 DIMPLIED("filtering true stack.\n");
606 *true_states = filter_stack(sm, pre_stree, false_stack, true_stack);
607 DIMPLIED("filtering false stack.\n");
608 *false_states = filter_stack(sm, pre_stree, true_stack, false_stack);
609 free_slist(&true_stack);
610 free_slist(&false_stack);
611
612 gettimeofday(&time_after, NULL);
613 sec = time_after.tv_sec - time_before.tv_sec;
614 if (option_timeout && sec > option_timeout) {
615 sm_perror("Function too hairy. Ignoring implications after %d seconds.", sec);
616 }
735 struct symbol *sym;
736 char *name;
737 struct sm_state *sm;
738 int mixed = 0;
739 int ret = 0;
740
741 if (expr->type == EXPR_POSTOP)
742 expr = strip_expr(expr->unop);
743
744 if (expr->type == EXPR_ASSIGNMENT) {
745 /* most of the time ->pools will be empty here because we
746 just set the state, but if have assigned a conditional
747 function there are implications. */
748 expr = expr->left;
749 }
750
751 name = expr_to_var_sym(expr, &sym);
752 if (!name || !sym)
753 goto free;
754 sm = get_sm_state(SMATCH_EXTRA, name, sym);
755 if (!sm)
756 goto free;
757
758 separate_and_filter(sm, SPECIAL_NOTEQUAL, tmp_range_list(estate_type(sm->state), 0), __get_cur_stree(), implied_true, implied_false, &mixed);
759 delete_gate_sm_equiv(implied_true, sm->name, sm->sym);
760 delete_gate_sm_equiv(implied_false, sm->name, sm->sym);
761 if (mixed) {
762 delete_gate_sm(implied_true, sm->name, sm->sym);
763 delete_gate_sm(implied_false, sm->name, sm->sym);
764 }
765
766 ret = 1;
767 free:
768 free_string(name);
769 return ret;
770 }
771
772 static int handled_by_comparison_hook(struct expression *expr,
773 struct stree **implied_true,
774 struct stree **implied_false)
775 {
776 struct state_list *true_stack = NULL;
777 struct state_list *false_stack = NULL;
778 struct stree *pre_stree;
779 struct sm_state *sm;
780
781 sm = comparison_implication_hook(expr, &true_stack, &false_stack);
782 if (!sm)
783 return 0;
784
785 pre_stree = clone_stree(__get_cur_stree());
786
787 *implied_true = filter_stack(sm, pre_stree, false_stack, true_stack);
788 *implied_false = filter_stack(sm, pre_stree, true_stack, false_stack);
789
790 free_stree(&pre_stree);
791 free_slist(&true_stack);
792 free_slist(&false_stack);
793
794 return 1;
795 }
796
797 static int handled_by_extra_states(struct expression *expr,
798 struct stree **implied_true,
799 struct stree **implied_false)
800 {
801 sval_t sval;
802
803 /* If the expression is known then it has no implications. */
804 if (get_implied_value(expr, &sval))
805 return true;
806
807 if (expr->type == EXPR_COMPARE)
808 return handle_comparison(expr, implied_true, implied_false);
809 else
936 FOR_EACH_SM(saved_implied_true, sm) {
937 __set_true_false_sm(sm, NULL);
938 } END_FOR_EACH_SM(sm);
939 free_stree(&saved_implied_true);
940
941 FOR_EACH_SM(saved_implied_false, sm) {
942 __set_true_false_sm(NULL, sm);
943 } END_FOR_EACH_SM(sm);
944 free_stree(&saved_implied_false);
945 }
946
947 static void set_extra_implied_states(struct expression *expr)
948 {
949 saved_implied_true = extra_saved_implied_true;
950 saved_implied_false = extra_saved_implied_false;
951 extra_saved_implied_true = NULL;
952 extra_saved_implied_false = NULL;
953 set_implied_states(NULL);
954 }
955
956 void param_limit_implications(struct expression *expr, int param, char *key, char *value)
957 {
958 struct expression *arg;
959 struct symbol *compare_type;
960 char *name;
961 struct symbol *sym;
962 struct sm_state *sm;
963 struct sm_state *tmp;
964 struct stree *implied_true = NULL;
965 struct stree *implied_false = NULL;
966 struct range_list *orig, *limit;
967
968 if (time_parsing_function() > 40)
969 return;
970
971 while (expr->type == EXPR_ASSIGNMENT)
972 expr = strip_expr(expr->right);
973 if (expr->type != EXPR_CALL)
974 return;
975
976 arg = get_argument_from_call_expr(expr->args, param);
977 if (!arg)
978 return;
979
980 arg = strip_parens(arg);
981 while (arg->type == EXPR_ASSIGNMENT && arg->op == '=')
982 arg = strip_parens(arg->left);
983
984 name = get_variable_from_key(arg, key, &sym);
985 if (!name || !sym)
986 goto free;
987
988 sm = get_sm_state(SMATCH_EXTRA, name, sym);
989 if (!sm || !sm->merged)
990 goto free;
991
992 if (strcmp(key, "$") == 0)
993 compare_type = get_arg_type(expr->fn, param);
994 else
995 compare_type = get_member_type_from_key(arg, key);
996
997 orig = estate_rl(sm->state);
998 orig = cast_rl(compare_type, orig);
999
1000 call_results_to_rl(expr, compare_type, value, &limit);
1001
1002 separate_and_filter(sm, SPECIAL_EQUAL, limit, __get_cur_stree(), &implied_true, &implied_false, NULL);
1003
1004 FOR_EACH_SM(implied_true, tmp) {
1005 __set_sm_fake_stree(tmp);
1006 } END_FOR_EACH_SM(tmp);
1007
1008 free_stree(&implied_true);
1009 free_stree(&implied_false);
1010 free:
1011 free_string(name);
1012 }
1013
1014 struct stree *__implied_case_stree(struct expression *switch_expr,
1015 struct range_list *rl,
1016 struct range_list_stack **remaining_cases,
1017 struct stree **raw_stree)
1018 {
1019 char *name;
1020 struct symbol *sym;
1021 struct var_sym_list *vsl;
1022 struct sm_state *sm;
1023 struct stree *true_states = NULL;
1024 struct stree *false_states = NULL;
|
55 * not have a ->pool.
56 * merge_sm_state() sets ->left and ->right. (These are the states which were
57 * merged to form the current state.)
58 * a pool: a pool is an slist that has been merged with another slist.
59 */
60
61 #include <time.h>
62 #include "smatch.h"
63 #include "smatch_slist.h"
64 #include "smatch_extra.h"
65
66 char *implied_debug_msg;
67
68 bool implications_off;
69
70 #define implied_debug 0
71 #define DIMPLIED(msg...) do { if (implied_debug) printf(msg); } while (0)
72
73 bool debug_implied(void)
74 {
75 if (option_debug)
76 return true;
77 return implied_debug;
78 }
79
80 /*
81 * tmp_range_list():
82 * It messes things up to free range list allocations. This helper fuction
83 * lets us reuse memory instead of doing new allocations.
84 */
85 static struct range_list *tmp_range_list(struct symbol *type, long long num)
86 {
87 static struct range_list *my_list = NULL;
88 static struct data_range *my_range;
89
90 __free_ptr_list((struct ptr_list **)&my_list);
91 my_range = alloc_range(ll_to_sval(num), ll_to_sval(num));
92 add_ptr_list(&my_list, my_range);
93 return my_list;
94 }
95
96 static const char *show_comparison(int op)
97 {
98 if (op == PARAM_LIMIT)
99 return "<lim>";
100 return show_special(op);
101 }
102
103 static void print_debug_tf(struct sm_state *sm, int istrue, int isfalse)
104 {
105 if (!implied_debug && !option_debug)
106 return;
107
108 if (istrue && isfalse) {
109 printf("%s: %d: does not exist.\n", show_sm(sm), sm->line);
110 } else if (istrue) {
111 printf("'%s = %s' from %d is true. %s[stree %d]\n", sm->name, show_state(sm->state),
112 sm->line, sm->merged ? "[merged]" : "[leaf]",
113 get_stree_id(sm->pool));
114 } else if (isfalse) {
115 printf("'%s = %s' from %d is false. %s[stree %d]\n", sm->name, show_state(sm->state),
116 sm->line,
117 sm->merged ? "[merged]" : "[leaf]",
118 get_stree_id(sm->pool));
119 } else {
120 printf("'%s = %s' from %d could be true or false. %s[stree %d]\n", sm->name,
121 show_state(sm->state), sm->line,
122 sm->merged ? "[merged]" : "[leaf]",
123 get_stree_id(sm->pool));
124 }
125 }
126
127 void split_comparison_helper(struct range_list *left_orig, int op, struct range_list *right_orig,
128 struct range_list **left_true_rl, struct range_list **left_false_rl)
129 {
130 if (op == PARAM_LIMIT) {
131 *left_true_rl = rl_intersection(left_orig, right_orig);
132 *left_false_rl = rl_filter(left_orig, right_orig);
133 return;
134 }
135
136 split_comparison_rl(left_orig, op, right_orig, left_true_rl, left_false_rl, NULL, NULL);
137 }
138
139 static int create_fake_history(struct sm_state *sm, int comparison, struct range_list *rl)
140 {
141 struct range_list *orig_rl;
142 struct range_list *true_rl, *false_rl;
143 struct stree *true_stree, *false_stree;
144 struct sm_state *true_sm, *false_sm;
145 sval_t sval;
146
147 if (is_merged(sm) || sm->left || sm->right)
148 return 0;
149 if (!rl_to_sval(rl, &sval))
150 return 0;
151 if (!estate_rl(sm->state))
152 return 0;
153
154 orig_rl = cast_rl(rl_type(rl), estate_rl(sm->state));
155 split_comparison_helper(orig_rl, comparison, rl, &true_rl, &false_rl);
156
157 true_rl = rl_truncate_cast(estate_type(sm->state), true_rl);
158 false_rl = rl_truncate_cast(estate_type(sm->state), false_rl);
159 if (is_whole_rl(true_rl) || is_whole_rl(false_rl) ||
160 !true_rl || !false_rl ||
161 rl_equiv(orig_rl, true_rl) || rl_equiv(orig_rl, false_rl) ||
162 rl_equiv(estate_rl(sm->state), true_rl) || rl_equiv(estate_rl(sm->state), false_rl))
163 return 0;
164
165 if (rl_intersection(true_rl, false_rl)) {
166 /*
167 * Normally these won't intersect, but one exception is when
168 * we're dealing with mtags. We have a long list of mtags and
169 * then negate the list. Now it's over the limit for mtag list
170 * length and we squash it down to 4096-ptr_max. So then it's
171 * possible for the true and false rl to overlap.
172 */
173 return 0;
174 }
175
176 if (implied_debug)
177 sm_msg("fake_history: %s vs %s. %s %s %s. --> T: %s F: %s",
178 sm->name, show_rl(rl), sm->state->name, show_comparison(comparison), show_rl(rl),
179 show_rl(true_rl), show_rl(false_rl));
180
181 true_sm = clone_sm(sm);
182 false_sm = clone_sm(sm);
183
184 true_sm->state = clone_partial_estate(sm->state, true_rl);
185 free_slist(&true_sm->possible);
186 add_possible_sm(true_sm, true_sm);
187 false_sm->state = clone_partial_estate(sm->state, false_rl);
188 free_slist(&false_sm->possible);
189 add_possible_sm(false_sm, false_sm);
190
191 true_stree = clone_stree(sm->pool);
192 false_stree = clone_stree(sm->pool);
193
194 overwrite_sm_state_stree(&true_stree, true_sm);
195 overwrite_sm_state_stree(&false_stree, false_sm);
196
197 true_sm->pool = true_stree;
198 false_sm->pool = false_stree;
237 return 1;
238 } END_FOR_EACH_PTR(tmp);
239 return 0;
240 }
241
242 static int remove_pool(struct state_list **pools, struct stree *remove)
243 {
244 struct sm_state *tmp;
245 int ret = 0;
246
247 FOR_EACH_PTR(*pools, tmp) {
248 if (tmp->pool == remove) {
249 DELETE_CURRENT_PTR(tmp);
250 ret = 1;
251 }
252 } END_FOR_EACH_PTR(tmp);
253
254 return ret;
255 }
256
257 static bool possibly_true_helper(struct range_list *var_rl, int comparison, struct range_list *rl)
258 {
259 if (comparison == PARAM_LIMIT) {
260 struct range_list *intersect;
261
262 intersect = rl_intersection(var_rl, rl);
263 if (intersect)
264 return true;
265 return false;
266 }
267 return possibly_true_rl(var_rl, comparison, rl);
268 }
269
270 static bool possibly_false_helper(struct range_list *var_rl, int comparison, struct range_list *rl)
271 {
272 if (comparison == PARAM_LIMIT) {
273 struct range_list *intersect;
274
275 intersect = rl_intersection(var_rl, rl);
276 if (!rl_equiv(var_rl, intersect))
277 return true;
278 return false;
279 }
280 return possibly_false_rl(var_rl, comparison, rl);
281 }
282
283 /*
284 * If 'foo' == 99 add it that pool to the true pools. If it's false, add it to
285 * the false pools. If we're not sure, then we don't add it to either.
286 */
287 static void do_compare(struct sm_state *sm, int comparison, struct range_list *rl,
288 struct state_list **true_stack,
289 struct state_list **maybe_stack,
290 struct state_list **false_stack,
291 int *mixed, struct sm_state *gate_sm)
292 {
293 int istrue;
294 int isfalse;
295 struct range_list *var_rl;
296
297 if (!sm->pool)
298 return;
299
300 var_rl = cast_rl(rl_type(rl), estate_rl(sm->state));
301
302 istrue = !possibly_false_helper(var_rl, comparison, rl);
303 isfalse = !possibly_true_helper(var_rl, comparison, rl);
304
305 print_debug_tf(sm, istrue, isfalse);
306
307 /* give up if we have borrowed implications (smatch_equiv.c) */
308 if (sm->sym != gate_sm->sym ||
309 strcmp(sm->name, gate_sm->name) != 0) {
310 if (mixed)
311 *mixed = 1;
312 }
313
314 if (mixed && !*mixed && !is_merged(sm) && !istrue && !isfalse) {
315 if (!create_fake_history(sm, comparison, rl))
316 *mixed = 1;
317 }
318
319 if (istrue)
320 add_pool(true_stack, sm);
321 else if (isfalse)
322 add_pool(false_stack, sm);
323 else
345 */
346 static void __separate_pools(struct sm_state *sm, int comparison, struct range_list *rl,
347 struct state_list **true_stack,
348 struct state_list **maybe_stack,
349 struct state_list **false_stack,
350 struct state_list **checked, int *mixed, struct sm_state *gate_sm,
351 struct timeval *start_time)
352 {
353 int free_checked = 0;
354 struct state_list *checked_states = NULL;
355 struct timeval now, diff;
356
357 if (!sm)
358 return;
359
360 gettimeofday(&now, NULL);
361 timersub(&now, start_time, &diff);
362 if (diff.tv_sec >= 1) {
363 if (implied_debug) {
364 sm_msg("debug: %s: implications taking too long. (%s %s %s)",
365 __func__, sm->state->name, show_comparison(comparison), show_rl(rl));
366 }
367 if (mixed)
368 *mixed = 1;
369 }
370
371 if (checked == NULL) {
372 checked = &checked_states;
373 free_checked = 1;
374 }
375 if (is_checked(*checked, sm))
376 return;
377 add_ptr_list(checked, sm);
378
379 do_compare(sm, comparison, rl, true_stack, maybe_stack, false_stack, mixed, gate_sm);
380
381 __separate_pools(sm->left, comparison, rl, true_stack, maybe_stack, false_stack, checked, mixed, gate_sm, start_time);
382 __separate_pools(sm->right, comparison, rl, true_stack, maybe_stack, false_stack, checked, mixed, gate_sm, start_time);
383 if (free_checked)
384 free_slist(checked);
385 }
623 avl_insert(&ret, filtered_sm);
624 } END_FOR_EACH_SM(tmp);
625 return ret;
626 }
627
628 static void separate_and_filter(struct sm_state *sm, int comparison, struct range_list *rl,
629 struct stree *pre_stree,
630 struct stree **true_states,
631 struct stree **false_states,
632 int *mixed)
633 {
634 struct state_list *true_stack = NULL;
635 struct state_list *false_stack = NULL;
636 struct timeval time_before;
637 struct timeval time_after;
638 int sec;
639
640 gettimeofday(&time_before, NULL);
641
642 DIMPLIED("checking implications: (%s (%s) %s %s)\n",
643 sm->name, sm->state->name, show_comparison(comparison), show_rl(rl));
644
645 if (!is_merged(sm)) {
646 DIMPLIED("%d '%s' from line %d is not merged.\n", get_lineno(), sm->name, sm->line);
647 return;
648 }
649
650 separate_pools(sm, comparison, rl, &true_stack, &false_stack, NULL, mixed);
651
652 DIMPLIED("filtering true stack.\n");
653 *true_states = filter_stack(sm, pre_stree, false_stack, true_stack);
654 DIMPLIED("filtering false stack.\n");
655 *false_states = filter_stack(sm, pre_stree, true_stack, false_stack);
656 free_slist(&true_stack);
657 free_slist(&false_stack);
658
659 gettimeofday(&time_after, NULL);
660 sec = time_after.tv_sec - time_before.tv_sec;
661 if (option_timeout && sec > option_timeout) {
662 sm_perror("Function too hairy. Ignoring implications after %d seconds.", sec);
663 }
782 struct symbol *sym;
783 char *name;
784 struct sm_state *sm;
785 int mixed = 0;
786 int ret = 0;
787
788 if (expr->type == EXPR_POSTOP)
789 expr = strip_expr(expr->unop);
790
791 if (expr->type == EXPR_ASSIGNMENT) {
792 /* most of the time ->pools will be empty here because we
793 just set the state, but if have assigned a conditional
794 function there are implications. */
795 expr = expr->left;
796 }
797
798 name = expr_to_var_sym(expr, &sym);
799 if (!name || !sym)
800 goto free;
801 sm = get_sm_state(SMATCH_EXTRA, name, sym);
802 if (!sm || !sm->merged)
803 goto free;
804
805 separate_and_filter(sm, SPECIAL_NOTEQUAL, tmp_range_list(estate_type(sm->state), 0), __get_cur_stree(), implied_true, implied_false, &mixed);
806 delete_gate_sm_equiv(implied_true, sm->name, sm->sym);
807 delete_gate_sm_equiv(implied_false, sm->name, sm->sym);
808 if (mixed) {
809 delete_gate_sm(implied_true, sm->name, sm->sym);
810 delete_gate_sm(implied_false, sm->name, sm->sym);
811 }
812
813 ret = 1;
814 free:
815 free_string(name);
816 return ret;
817 }
818
819 static int handled_by_comparison_hook(struct expression *expr,
820 struct stree **implied_true,
821 struct stree **implied_false)
822 {
823 struct sm_state *sm, *true_sm, *false_sm;
824 struct state_list *true_stack = NULL;
825 struct state_list *false_stack = NULL;
826 struct stree *pre_stree;
827
828 sm = comparison_implication_hook(expr, &true_stack, &false_stack);
829 if (!sm)
830 return 0;
831
832 pre_stree = clone_stree(__get_cur_stree());
833
834 *implied_true = filter_stack(sm, pre_stree, false_stack, true_stack);
835 *implied_false = filter_stack(sm, pre_stree, true_stack, false_stack);
836
837 true_sm = get_sm_state_stree(*implied_true, sm->owner, sm->name, sm->sym);
838 false_sm = get_sm_state_stree(*implied_false, sm->owner, sm->name, sm->sym);
839 if (true_sm && strcmp(true_sm->state->name, "unknown") == 0)
840 delete_state_stree(implied_true, sm->owner, sm->name, sm->sym);
841 if (false_sm && strcmp(false_sm->state->name, "unknown") == 0)
842 delete_state_stree(implied_false, sm->owner, sm->name, sm->sym);
843
844 free_stree(&pre_stree);
845 free_slist(&true_stack);
846 free_slist(&false_stack);
847
848 return 1;
849 }
850
851 static int handled_by_extra_states(struct expression *expr,
852 struct stree **implied_true,
853 struct stree **implied_false)
854 {
855 sval_t sval;
856
857 /* If the expression is known then it has no implications. */
858 if (get_implied_value(expr, &sval))
859 return true;
860
861 if (expr->type == EXPR_COMPARE)
862 return handle_comparison(expr, implied_true, implied_false);
863 else
990 FOR_EACH_SM(saved_implied_true, sm) {
991 __set_true_false_sm(sm, NULL);
992 } END_FOR_EACH_SM(sm);
993 free_stree(&saved_implied_true);
994
995 FOR_EACH_SM(saved_implied_false, sm) {
996 __set_true_false_sm(NULL, sm);
997 } END_FOR_EACH_SM(sm);
998 free_stree(&saved_implied_false);
999 }
1000
1001 static void set_extra_implied_states(struct expression *expr)
1002 {
1003 saved_implied_true = extra_saved_implied_true;
1004 saved_implied_false = extra_saved_implied_false;
1005 extra_saved_implied_true = NULL;
1006 extra_saved_implied_false = NULL;
1007 set_implied_states(NULL);
1008 }
1009
1010 void param_limit_implications(struct expression *expr, int param, char *key, char *value, struct stree **implied)
1011 {
1012 struct expression *orig_expr, *arg;
1013 struct symbol *compare_type;
1014 char *name;
1015 struct symbol *sym;
1016 struct sm_state *sm;
1017 struct sm_state *tmp;
1018 struct stree *implied_true = NULL;
1019 struct stree *implied_false = NULL;
1020 struct range_list *orig, *limit;
1021 char *left_name = NULL;
1022 struct symbol *left_sym = NULL;
1023 int mixed = 0;
1024
1025 if (time_parsing_function() > 40)
1026 return;
1027
1028 orig_expr = expr;
1029 while (expr->type == EXPR_ASSIGNMENT)
1030 expr = strip_expr(expr->right);
1031 if (expr->type != EXPR_CALL)
1032 return;
1033
1034 arg = get_argument_from_call_expr(expr->args, param);
1035 if (!arg)
1036 return;
1037
1038 arg = strip_parens(arg);
1039 while (arg->type == EXPR_ASSIGNMENT && arg->op == '=')
1040 arg = strip_parens(arg->left);
1041
1042 name = get_variable_from_key(arg, key, &sym);
1043 if (!name || !sym)
1044 goto free;
1045
1046 sm = get_sm_state(SMATCH_EXTRA, name, sym);
1047 if (!sm || !sm->merged)
1048 goto free;
1049
1050 if (strcmp(key, "$") == 0)
1051 compare_type = get_arg_type(expr->fn, param);
1052 else
1053 compare_type = get_member_type_from_key(arg, key);
1054
1055 orig = estate_rl(sm->state);
1056 orig = cast_rl(compare_type, orig);
1057
1058 call_results_to_rl(expr, compare_type, value, &limit);
1059
1060 separate_and_filter(sm, PARAM_LIMIT, limit, __get_cur_stree(), &implied_true, &implied_false, &mixed);
1061
1062 if (orig_expr->type == EXPR_ASSIGNMENT)
1063 left_name = expr_to_var_sym(orig_expr->left, &left_sym);
1064
1065 FOR_EACH_SM(implied_true, tmp) {
1066 /*
1067 * What we're trying to do here is preserve the sm state so that
1068 * smatch extra doesn't create a new sm state when it parses the
1069 * PARAM_LIMIT.
1070 */
1071 if (!mixed && tmp->sym == sym &&
1072 strcmp(tmp->name, name) == 0 &&
1073 (!left_name || strcmp(left_name, name) != 0)) {
1074 overwrite_sm_state_stree(implied, tmp);
1075 continue;
1076 }
1077
1078 // TODO why can't this just be __set_sm()?
1079 __set_sm_fake_stree(tmp);
1080 } END_FOR_EACH_SM(tmp);
1081
1082 free_stree(&implied_true);
1083 free_stree(&implied_false);
1084 free:
1085 free_string(name);
1086 }
1087
1088 struct stree *__implied_case_stree(struct expression *switch_expr,
1089 struct range_list *rl,
1090 struct range_list_stack **remaining_cases,
1091 struct stree **raw_stree)
1092 {
1093 char *name;
1094 struct symbol *sym;
1095 struct var_sym_list *vsl;
1096 struct sm_state *sm;
1097 struct stree *true_states = NULL;
1098 struct stree *false_states = NULL;
|