?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
math: silence hard max false positives
[smatch.git] / smatch_comparison.c
blob65d880e9d49dbb20509b8ec8f67cc5169fcaa3f6
1 /*
2 * Copyright (C) 2012 Oracle.
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 * The point here is to store the relationships between two variables.
20 * Ie: y > x.
21 * To do that we create a state with the two variables in alphabetical order:
22 * ->name = "x vs y" and the state would be "<". On the false path the state
23 * would be ">=".
24 *
25 * Part of the trick of it is that if x or y is modified then we need to reset
26 * the state. We need to keep a list of all the states which depend on x and
27 * all the states which depend on y. The link_id code handles this.
28 *
29 */
30
31 #include "smatch.h"
32 #include "smatch_extra.h"
33 #include "smatch_slist.h"
34
35 static int compare_id;
36 static int link_id;
37 static int inc_dec_id;
38 static int inc_dec_link_id;
39
40 /* for handling for loops */
41 STATE(start);
42 STATE(incremented);
43
44 ALLOCATOR(compare_data, "compare data");
45
46 static struct symbol *vsl_to_sym(struct var_sym_list *vsl)
47 {
48 struct var_sym *vs;
49
50 if (!vsl)
51 return NULL;
52 if (ptr_list_size((struct ptr_list *)vsl) != 1)
53 return NULL;
54 vs = first_ptr_list((struct ptr_list *)vsl);
55 return vs->sym;
56 }
57
58 struct smatch_state *alloc_compare_state(
59 struct expression *left,
60 const char *left_var, struct var_sym_list *left_vsl,
61 int comparison,
62 struct expression *right,
63 const char *right_var, struct var_sym_list *right_vsl)
64 {
65 struct smatch_state *state;
66 struct compare_data *data;
67
68 state = __alloc_smatch_state(0);
69 state->name = alloc_sname(show_special(comparison));
70 data = __alloc_compare_data(0);
71 data->left = left;
72 data->left_var = alloc_sname(left_var);
73 data->left_vsl = clone_var_sym_list(left_vsl);
74 data->comparison = comparison;
75 data->right = right;
76 data->right_var = alloc_sname(right_var);
77 data->right_vsl = clone_var_sym_list(right_vsl);
78 state->data = data;
79 return state;
80 }
81
82 int state_to_comparison(struct smatch_state *state)
83 {
84 if (!state || !state->data)
85 return 0;
86 return ((struct compare_data *)state->data)->comparison;
87 }
88
89 /*
90 * flip_comparison() reverses the op left and right. So "x >= y" becomes "y <= x".
91 */
92 int flip_comparison(int op)
93 {
94 switch (op) {
95 case 0:
96 return 0;
97 case '<':
98 return '>';
99 case SPECIAL_UNSIGNED_LT:
100 return SPECIAL_UNSIGNED_GT;
101 case SPECIAL_LTE:
102 return SPECIAL_GTE;
103 case SPECIAL_UNSIGNED_LTE:
104 return SPECIAL_UNSIGNED_GTE;
105 case SPECIAL_EQUAL:
106 return SPECIAL_EQUAL;
107 case SPECIAL_NOTEQUAL:
108 return SPECIAL_NOTEQUAL;
109 case SPECIAL_GTE:
110 return SPECIAL_LTE;
111 case SPECIAL_UNSIGNED_GTE:
112 return SPECIAL_UNSIGNED_LTE;
113 case '>':
114 return '<';
115 case SPECIAL_UNSIGNED_GT:
116 return SPECIAL_UNSIGNED_LT;
117 default:
118 sm_msg("internal smatch bug. unhandled comparison %d", op);
119 return op;
120 }
121 }
122
123 int negate_comparison(int op)
124 {
125 switch (op) {
126 case 0:
127 return 0;
128 case '<':
129 return SPECIAL_GTE;
130 case SPECIAL_UNSIGNED_LT:
131 return SPECIAL_UNSIGNED_GTE;
132 case SPECIAL_LTE:
133 return '>';
134 case SPECIAL_UNSIGNED_LTE:
135 return SPECIAL_UNSIGNED_GT;
136 case SPECIAL_EQUAL:
137 return SPECIAL_NOTEQUAL;
138 case SPECIAL_NOTEQUAL:
139 return SPECIAL_EQUAL;
140 case SPECIAL_GTE:
141 return '<';
142 case SPECIAL_UNSIGNED_GTE:
143 return SPECIAL_UNSIGNED_LT;
144 case '>':
145 return SPECIAL_LTE;
146 case SPECIAL_UNSIGNED_GT:
147 return SPECIAL_UNSIGNED_LTE;
148 default:
149 sm_msg("internal smatch bug. unhandled comparison %d", op);
150 return op;
151 }
152 }
153
154 static int rl_comparison(struct range_list *left_rl, struct range_list *right_rl)
155 {
156 sval_t left_min, left_max, right_min, right_max;
157
158 if (!left_rl || !right_rl)
159 return 0;
160
161 left_min = rl_min(left_rl);
162 left_max = rl_max(left_rl);
163 right_min = rl_min(right_rl);
164 right_max = rl_max(right_rl);
165
166 if (left_min.value == left_max.value &&
167 right_min.value == right_max.value &&
168 left_min.value == right_min.value)
169 return SPECIAL_EQUAL;
170
171 if (sval_cmp(left_max, right_min) < 0)
172 return '<';
173 if (sval_cmp(left_max, right_min) == 0)
174 return SPECIAL_LTE;
175 if (sval_cmp(left_min, right_max) > 0)
176 return '>';
177 if (sval_cmp(left_min, right_max) == 0)
178 return SPECIAL_GTE;
179
180 return 0;
181 }
182
183 static struct range_list *get_orig_rl(struct var_sym_list *vsl)
184 {
185 struct symbol *sym;
186 struct smatch_state *state;
187
188 if (!vsl)
189 return NULL;
190 sym = vsl_to_sym(vsl);
191 if (!sym || !sym->ident)
192 return NULL;
193 state = get_orig_estate(sym->ident->name, sym);
194 return estate_rl(state);
195 }
196
197 static struct smatch_state *unmatched_comparison(struct sm_state *sm)
198 {
199 struct compare_data *data = sm->state->data;
200 struct range_list *left_rl, *right_rl;
201 int op;
202
203 if (!data)
204 return &undefined;
205
206 if (strstr(data->left_var, " orig"))
207 left_rl = get_orig_rl(data->left_vsl);
208 else if (!get_implied_rl_var_sym(data->left_var, vsl_to_sym(data->left_vsl), &left_rl))
209 return &undefined;
210 if (strstr(data->right_var, " orig"))
211 right_rl = get_orig_rl(data->right_vsl);
212 else if (!get_implied_rl_var_sym(data->right_var, vsl_to_sym(data->right_vsl), &right_rl))
213 return &undefined;
214
215 op = rl_comparison(left_rl, right_rl);
216 if (op)
217 return alloc_compare_state(
218 data->left, data->left_var, data->left_vsl,
219 op,
220 data->right, data->right_var, data->right_vsl);
221
222 return &undefined;
223 }
224
225 /* remove_unsigned_from_comparison() is obviously a hack. */
226 int remove_unsigned_from_comparison(int op)
227 {
228 switch (op) {
229 case SPECIAL_UNSIGNED_LT:
230 return '<';
231 case SPECIAL_UNSIGNED_LTE:
232 return SPECIAL_LTE;
233 case SPECIAL_UNSIGNED_GTE:
234 return SPECIAL_GTE;
235 case SPECIAL_UNSIGNED_GT:
236 return '>';
237 default:
238 return op;
239 }
240 }
241
242 /*
243 * This is for when you merge states "a < b" and "a == b", the result is that
244 * we can say for sure, "a <= b" after the merge.
245 */
246 int merge_comparisons(int one, int two)
247 {
248 int LT, EQ, GT;
249
250 if (!one || !two)
251 return 0;
252
253 one = remove_unsigned_from_comparison(one);
254 two = remove_unsigned_from_comparison(two);
255
256 if (one == two)
257 return one;
258
259 LT = EQ = GT = 0;
260
261 switch (one) {
262 case '<':
263 LT = 1;
264 break;
265 case SPECIAL_LTE:
266 LT = 1;
267 EQ = 1;
268 break;
269 case SPECIAL_EQUAL:
270 EQ = 1;
271 break;
272 case SPECIAL_GTE:
273 GT = 1;
274 EQ = 1;
275 break;
276 case '>':
277 GT = 1;
278 }
279
280 switch (two) {
281 case '<':
282 LT = 1;
283 break;
284 case SPECIAL_LTE:
285 LT = 1;
286 EQ = 1;
287 break;
288 case SPECIAL_EQUAL:
289 EQ = 1;
290 break;
291 case SPECIAL_GTE:
292 GT = 1;
293 EQ = 1;
294 break;
295 case '>':
296 GT = 1;
297 }
298
299 if (LT && EQ && GT)
300 return 0;
301 if (LT && EQ)
302 return SPECIAL_LTE;
303 if (LT && GT)
304 return SPECIAL_NOTEQUAL;
305 if (LT)
306 return '<';
307 if (EQ && GT)
308 return SPECIAL_GTE;
309 if (GT)
310 return '>';
311 return 0;
312 }
313
314 /*
315 * This is for if you have "a < b" and "b <= c". Or in other words,
316 * "a < b <= c". You would call this like get_combined_comparison('<', '<=').
317 * The return comparison would be '<'.
318 *
319 * This function is different from merge_comparisons(), for example:
320 * merge_comparison('<', '==') returns '<='
321 * get_combined_comparison('<', '==') returns '<'
322 */
323 int combine_comparisons(int left_compare, int right_compare)
324 {
325 int LT, EQ, GT;
326
327 left_compare = remove_unsigned_from_comparison(left_compare);
328 right_compare = remove_unsigned_from_comparison(right_compare);
329
330 LT = EQ = GT = 0;
331
332 switch (left_compare) {
333 case '<':
334 LT++;
335 break;
336 case SPECIAL_LTE:
337 LT++;
338 EQ++;
339 break;
340 case SPECIAL_EQUAL:
341 return right_compare;
342 case SPECIAL_GTE:
343 GT++;
344 EQ++;
345 break;
346 case '>':
347 GT++;
348 }
349
350 switch (right_compare) {
351 case '<':
352 LT++;
353 break;
354 case SPECIAL_LTE:
355 LT++;
356 EQ++;
357 break;
358 case SPECIAL_EQUAL:
359 return left_compare;
360 case SPECIAL_GTE:
361 GT++;
362 EQ++;
363 break;
364 case '>':
365 GT++;
366 }
367
368 if (LT == 2) {
369 if (EQ == 2)
370 return SPECIAL_LTE;
371 return '<';
372 }
373
374 if (GT == 2) {
375 if (EQ == 2)
376 return SPECIAL_GTE;
377 return '>';
378 }
379 return 0;
380 }
381
382 static int filter_comparison(int orig, int op)
383 {
384 if (orig == op)
385 return orig;
386
387 switch (orig) {
388 case 0:
389 return op;
390 case '<':
391 switch (op) {
392 case '<':
393 case SPECIAL_LTE:
394 case SPECIAL_NOTEQUAL:
395 return '<';
396 }
397 return 0;
398 case SPECIAL_LTE:
399 switch (op) {
400 case '<':
401 case SPECIAL_LTE:
402 case SPECIAL_EQUAL:
403 return op;
404 case SPECIAL_NOTEQUAL:
405 return '<';
406 }
407 return 0;
408 case SPECIAL_EQUAL:
409 switch (op) {
410 case SPECIAL_LTE:
411 case SPECIAL_EQUAL:
412 case SPECIAL_GTE:
413 case SPECIAL_UNSIGNED_LTE:
414 case SPECIAL_UNSIGNED_GTE:
415 return SPECIAL_EQUAL;
416 }
417 return 0;
418 case SPECIAL_NOTEQUAL:
419 switch (op) {
420 case '<':
421 case SPECIAL_LTE:
422 return '<';
423 case SPECIAL_UNSIGNED_LT:
424 case SPECIAL_UNSIGNED_LTE:
425 return SPECIAL_UNSIGNED_LT;
426 case SPECIAL_NOTEQUAL:
427 return op;
428 case '>':
429 case SPECIAL_GTE:
430 return '>';
431 case SPECIAL_UNSIGNED_GT:
432 case SPECIAL_UNSIGNED_GTE:
433 return SPECIAL_UNSIGNED_GT;
434 }
435 return 0;
436 case SPECIAL_GTE:
437 switch (op) {
438 case SPECIAL_LTE:
439 return SPECIAL_EQUAL;
440 case '>':
441 case SPECIAL_GTE:
442 case SPECIAL_EQUAL:
443 return op;
444 case SPECIAL_NOTEQUAL:
445 return '>';
446 }
447 return 0;
448 case '>':
449 switch (op) {
450 case '>':
451 case SPECIAL_GTE:
452 case SPECIAL_NOTEQUAL:
453 return '>';
454 }
455 return 0;
456 case SPECIAL_UNSIGNED_LT:
457 switch (op) {
458 case SPECIAL_UNSIGNED_LT:
459 case SPECIAL_UNSIGNED_LTE:
460 case SPECIAL_NOTEQUAL:
461 return SPECIAL_UNSIGNED_LT;
462 }
463 return 0;
464 case SPECIAL_UNSIGNED_LTE:
465 switch (op) {
466 case SPECIAL_UNSIGNED_LT:
467 case SPECIAL_UNSIGNED_LTE:
468 case SPECIAL_EQUAL:
469 return op;
470 case SPECIAL_NOTEQUAL:
471 return SPECIAL_UNSIGNED_LT;
472 case SPECIAL_UNSIGNED_GTE:
473 return SPECIAL_EQUAL;
474 }
475 return 0;
476 case SPECIAL_UNSIGNED_GTE:
477 switch (op) {
478 case SPECIAL_UNSIGNED_LTE:
479 return SPECIAL_EQUAL;
480 case SPECIAL_NOTEQUAL:
481 return SPECIAL_UNSIGNED_GT;
482 case SPECIAL_EQUAL:
483 case SPECIAL_UNSIGNED_GTE:
484 case SPECIAL_UNSIGNED_GT:
485 return op;
486 }
487 return 0;
488 case SPECIAL_UNSIGNED_GT:
489 switch (op) {
490 case SPECIAL_UNSIGNED_GT:
491 case SPECIAL_UNSIGNED_GTE:
492 case SPECIAL_NOTEQUAL:
493 return SPECIAL_UNSIGNED_GT;
494 }
495 return 0;
496 }
497 return 0;
498 }
499
500 struct smatch_state *merge_compare_states(struct smatch_state *s1, struct smatch_state *s2)
501 {
502 struct compare_data *data = s1->data;
503 int op;
504
505 op = merge_comparisons(state_to_comparison(s1), state_to_comparison(s2));
506 if (op)
507 return alloc_compare_state(
508 data->left, data->left_var, data->left_vsl,
509 op,
510 data->right, data->right_var, data->right_vsl);
511 return &undefined;
512 }
513
514 static struct smatch_state *alloc_link_state(struct string_list *links)
515 {
516 struct smatch_state *state;
517 static char buf[256];
518 char *tmp;
519 int i;
520
521 state = __alloc_smatch_state(0);
522
523 i = 0;
524 FOR_EACH_PTR(links, tmp) {
525 if (!i++) {
526 snprintf(buf, sizeof(buf), "%s", tmp);
527 } else {
528 append(buf, ", ", sizeof(buf));
529 append(buf, tmp, sizeof(buf));
530 }
531 } END_FOR_EACH_PTR(tmp);
532
533 state->name = alloc_sname(buf);
534 state->data = links;
535 return state;
536 }
537
538 static void save_start_states(struct statement *stmt)
539 {
540 struct symbol *param;
541 char orig[64];
542 char state_name[128];
543 struct smatch_state *state;
544 struct string_list *links;
545 char *link;
546
547 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
548 struct var_sym_list *left_vsl = NULL;
549 struct var_sym_list *right_vsl = NULL;
550
551 if (!param->ident)
552 continue;
553 snprintf(orig, sizeof(orig), "%s orig", param->ident->name);
554 snprintf(state_name, sizeof(state_name), "%s vs %s", param->ident->name, orig);
555 add_var_sym(&left_vsl, param->ident->name, param);
556 add_var_sym(&right_vsl, orig, param);
557 state = alloc_compare_state(
558 NULL, param->ident->name, left_vsl,
559 SPECIAL_EQUAL,
560 NULL, alloc_sname(orig), right_vsl);
561 set_state(compare_id, state_name, NULL, state);
562
563 link = alloc_sname(state_name);
564 links = NULL;
565 insert_string(&links, link);
566 state = alloc_link_state(links);
567 set_state(link_id, param->ident->name, param, state);
568 } END_FOR_EACH_PTR(param);
569 }
570
571 static struct smatch_state *merge_links(struct smatch_state *s1, struct smatch_state *s2)
572 {
573 struct smatch_state *ret;
574 struct string_list *links;
575
576 links = combine_string_lists(s1->data, s2->data);
577 ret = alloc_link_state(links);
578 return ret;
579 }
580
581 static void save_link_var_sym(const char *var, struct symbol *sym, const char *link)
582 {
583 struct smatch_state *old_state, *new_state;
584 struct string_list *links;
585 char *new;
586
587 old_state = get_state(link_id, var, sym);
588 if (old_state)
589 links = clone_str_list(old_state->data);
590 else
591 links = NULL;
592
593 new = alloc_sname(link);
594 insert_string(&links, new);
595
596 new_state = alloc_link_state(links);
597 set_state(link_id, var, sym, new_state);
598 }
599
600 static void match_inc(struct sm_state *sm)
601 {
602 struct string_list *links;
603 struct smatch_state *state;
604 char *tmp;
605 int flip;
606 int op;
607
608 links = sm->state->data;
609
610 FOR_EACH_PTR(links, tmp) {
611 state = get_state(compare_id, tmp, NULL);
612
613 flip = 0;
614 if (strncmp(sm->name, tmp, strlen(sm->name)) != 0 ||
615 tmp[strlen(sm->name)] != ' ')
616 flip = 1;
617
618 op = state_to_comparison(state);
619
620 switch (flip ? flip_comparison(op) : op) {
621 case SPECIAL_EQUAL:
622 case SPECIAL_GTE:
623 case SPECIAL_UNSIGNED_GTE:
624 case '>':
625 case SPECIAL_UNSIGNED_GT: {
626 struct compare_data *data = state->data;
627 struct smatch_state *new;
628
629 new = alloc_compare_state(
630 data->left, data->left_var, data->left_vsl,
631 flip ? '<' : '>',
632 data->right, data->right_var, data->right_vsl);
633 set_state(compare_id, tmp, NULL, new);
634 break;
635 }
636 default:
637 set_state(compare_id, tmp, NULL, &undefined);
638 }
639 } END_FOR_EACH_PTR(tmp);
640 }
641
642 static void match_dec(struct sm_state *sm)
643 {
644 struct string_list *links;
645 struct smatch_state *state;
646 char *tmp;
647
648 links = sm->state->data;
649
650 FOR_EACH_PTR(links, tmp) {
651 state = get_state(compare_id, tmp, NULL);
652
653 switch (state_to_comparison(state)) {
654 case SPECIAL_EQUAL:
655 case SPECIAL_LTE:
656 case SPECIAL_UNSIGNED_LTE:
657 case '<':
658 case SPECIAL_UNSIGNED_LT: {
659 struct compare_data *data = state->data;
660 struct smatch_state *new;
661
662 new = alloc_compare_state(
663 data->left, data->left_var, data->left_vsl,
664 '<',
665 data->right, data->right_var, data->right_vsl);
666 set_state(compare_id, tmp, NULL, new);
667 break;
668 }
669 default:
670 set_state(compare_id, tmp, NULL, &undefined);
671 }
672 } END_FOR_EACH_PTR(tmp);
673 }
674
675 static int match_inc_dec(struct sm_state *sm, struct expression *mod_expr)
676 {
677 if (!mod_expr)
678 return 0;
679 if (mod_expr->type != EXPR_PREOP && mod_expr->type != EXPR_POSTOP)
680 return 0;
681
682 if (mod_expr->op == SPECIAL_INCREMENT) {
683 match_inc(sm);
684 return 1;
685 }
686 if (mod_expr->op == SPECIAL_DECREMENT) {
687 match_dec(sm);
688 return 1;
689 }
690 return 0;
691 }
692
693 static void match_modify(struct sm_state *sm, struct expression *mod_expr)
694 {
695 struct string_list *links;
696 char *tmp;
697
698 /*
699 * if (foo > bar) then ++foo is also > bar.
700 */
701 if (match_inc_dec(sm, mod_expr))
702 return;
703
704 links = sm->state->data;
705
706 FOR_EACH_PTR(links, tmp) {
707 set_state(compare_id, tmp, NULL, &undefined);
708 } END_FOR_EACH_PTR(tmp);
709 set_state(link_id, sm->name, sm->sym, &undefined);
710 }
711
712 static char *chunk_to_var_sym(struct expression *expr, struct symbol **sym)
713 {
714 expr = strip_expr(expr);
715 if (!expr)
716 return NULL;
717 if (sym)
718 *sym = NULL;
719
720 if (expr->type == EXPR_PREOP &&
721 (expr->op == SPECIAL_INCREMENT ||
722 expr->op == SPECIAL_DECREMENT))
723 expr = strip_expr(expr->unop);
724
725 if (expr->type == EXPR_CALL) {
726 char buf[64];
727
728 snprintf(buf, sizeof(buf), "return %p", expr);
729 return alloc_string(buf);
730 }
731
732 return expr_to_chunk_sym_vsl(expr, sym, NULL);
733 }
734
735 static char *chunk_to_var(struct expression *expr)
736 {
737 return chunk_to_var_sym(expr, NULL);
738 }
739
740 static struct smatch_state *get_state_chunk(int owner, struct expression *expr)
741 {
742 char *name;
743 struct symbol *sym;
744 struct smatch_state *ret;
745
746 name = chunk_to_var_sym(expr, &sym);
747 if (!name)
748 return NULL;
749
750 ret = get_state(owner, name, sym);
751 free_string(name);
752 return ret;
753 }
754
755 static void save_link(struct expression *expr, char *link)
756 {
757 char *var;
758 struct symbol *sym;
759
760 expr = strip_expr(expr);
761 if (expr->type == EXPR_BINOP) {
762 char *chunk;
763
764 chunk = chunk_to_var(expr);
765 if (!chunk)
766 return;
767
768 save_link(expr->left, link);
769 save_link(expr->right, link);
770 save_link_var_sym(chunk, NULL, link);
771 return;
772 }
773
774 var = chunk_to_var_sym(expr, &sym);
775 if (!var)
776 return;
777
778 save_link_var_sym(var, sym, link);
779 free_string(var);
780 }
781
782 static int get_orig_comparison(struct stree *pre_stree, const char *left, const char *right)
783 {
784 struct smatch_state *state;
785 struct compare_data *data;
786 int flip = 0;
787 char state_name[256];
788
789 if (strcmp(left, right) > 0) {
790 const char *tmp = right;
791
792 flip = 1;
793 right = left;
794 left = tmp;
795 }
796
797 snprintf(state_name, sizeof(state_name), "%s vs %s", left, right);
798 state = get_state_stree(pre_stree, compare_id, state_name, NULL);
799 if (!state || !state->data)
800 return 0;
801 data = state->data;
802 if (flip)
803 return flip_comparison(data->comparison);
804 return data->comparison;
805
806 }
807
808 static int have_common_var_sym(struct var_sym_list *left_vsl, struct var_sym_list *right_vsl)
809 {
810 struct var_sym *tmp;
811
812 FOR_EACH_PTR(left_vsl, tmp) {
813 if (in_var_sym_list(right_vsl, tmp->var, tmp->sym))
814 return 1;
815 } END_FOR_EACH_PTR(tmp);
816
817 return 0;
818 }
819
820 /*
821 * The idea here is that we take a comparison "a < b" and then we look at all
822 * the things which "b" is compared against "b < c" and we say that that implies
823 * a relationship "a < c".
824 *
825 * The names here about because the comparisons are organized like this
826 * "a < b < c".
827 *
828 */
829 static void update_tf_links(struct stree *pre_stree,
830 struct expression *left_expr,
831 const char *left_var, struct var_sym_list *left_vsl,
832 int left_comparison, int left_false_comparison,
833 const char *mid_var, struct var_sym_list *mid_vsl,
834 struct string_list *links)
835 {
836 struct smatch_state *state;
837 struct smatch_state *true_state, *false_state;
838 struct compare_data *data;
839 struct expression *right_expr;
840 const char *right_var;
841 struct var_sym_list *right_vsl;
842 int orig_comparison;
843 int right_comparison;
844 int true_comparison;
845 int false_comparison;
846 char *tmp;
847 char state_name[256];
848 struct var_sym *vs;
849
850 FOR_EACH_PTR(links, tmp) {
851 state = get_state_stree(pre_stree, compare_id, tmp, NULL);
852 if (!state || !state->data)
853 continue;
854 data = state->data;
855 right_comparison = data->comparison;
856 right_expr = data->right;
857 right_var = data->right_var;
858 right_vsl = data->right_vsl;
859 if (strcmp(mid_var, right_var) == 0) {
860 right_expr = data->left;
861 right_var = data->left_var;
862 right_vsl = data->left_vsl;
863 right_comparison = flip_comparison(right_comparison);
864 }
865 if (have_common_var_sym(left_vsl, right_vsl))
866 continue;
867
868 orig_comparison = get_orig_comparison(pre_stree, left_var, right_var);
869
870 true_comparison = combine_comparisons(left_comparison, right_comparison);
871 false_comparison = combine_comparisons(left_false_comparison, right_comparison);
872
873 true_comparison = filter_comparison(orig_comparison, true_comparison);
874 false_comparison = filter_comparison(orig_comparison, false_comparison);
875
876 if (strcmp(left_var, right_var) > 0) {
877 struct expression *tmp_expr = left_expr;
878 const char *tmp_var = left_var;
879 struct var_sym_list *tmp_vsl = left_vsl;
880
881 left_expr = right_expr;
882 left_var = right_var;
883 left_vsl = right_vsl;
884 right_expr = tmp_expr;
885 right_var = tmp_var;
886 right_vsl = tmp_vsl;
887 true_comparison = flip_comparison(true_comparison);
888 false_comparison = flip_comparison(false_comparison);
889 }
890
891 if (!true_comparison && !false_comparison)
892 continue;
893
894 if (true_comparison)
895 true_state = alloc_compare_state(
896 left_expr, left_var, left_vsl,
897 true_comparison,
898 right_expr, right_var, right_vsl);
899 else
900 true_state = NULL;
901 if (false_comparison)
902 false_state = alloc_compare_state(
903 left_expr, left_var, left_vsl,
904 false_comparison,
905 right_expr, right_var, right_vsl);
906 else
907 false_state = NULL;
908
909 snprintf(state_name, sizeof(state_name), "%s vs %s", left_var, right_var);
910 set_true_false_states(compare_id, state_name, NULL, true_state, false_state);
911 FOR_EACH_PTR(left_vsl, vs) {
912 save_link_var_sym(vs->var, vs->sym, state_name);
913 } END_FOR_EACH_PTR(vs);
914 FOR_EACH_PTR(right_vsl, vs) {
915 save_link_var_sym(vs->var, vs->sym, state_name);
916 } END_FOR_EACH_PTR(vs);
917 if (!vsl_to_sym(left_vsl))
918 save_link_var_sym(left_var, NULL, state_name);
919 if (!vsl_to_sym(right_vsl))
920 save_link_var_sym(right_var, NULL, state_name);
921 } END_FOR_EACH_PTR(tmp);
922 }
923
924 static void update_tf_data(struct stree *pre_stree,
925 struct expression *left_expr,
926 const char *left_name, struct var_sym_list *left_vsl,
927 struct expression *right_expr,
928 const char *right_name, struct var_sym_list *right_vsl,
929 int true_comparison, int false_comparison)
930 {
931 struct smatch_state *state;
932
933 state = get_state_stree(pre_stree, link_id, right_name, vsl_to_sym(right_vsl));
934 if (state)
935 update_tf_links(pre_stree, left_expr, left_name, left_vsl, true_comparison, false_comparison, right_name, right_vsl, state->data);
936
937 state = get_state_stree(pre_stree, link_id, left_name, vsl_to_sym(left_vsl));
938 if (state)
939 update_tf_links(pre_stree, right_expr, right_name, right_vsl, flip_comparison(true_comparison), flip_comparison(false_comparison), left_name, left_vsl, state->data);
940 }
941
942 static void iter_modify(struct sm_state *sm, struct expression *mod_expr)
943 {
944 if (sm->state != &start ||
945 !mod_expr ||
946 (mod_expr->type != EXPR_PREOP && mod_expr->type != EXPR_POSTOP) ||
947 mod_expr->op != SPECIAL_INCREMENT)
948 set_state(inc_dec_id, sm->name, sm->sym, &undefined);
949 else
950 set_state(inc_dec_id, sm->name, sm->sym, &incremented);
951 }
952
953 static void handle_for_loops(struct expression *expr, char *state_name, struct smatch_state *false_state)
954 {
955 sval_t sval;
956 char *iter_name, *cap_name;
957 struct symbol *iter_sym, *cap_sym;
958 struct compare_data *data;
959
960 if (expr->op != '<' && expr->op != SPECIAL_UNSIGNED_LT)
961 return;
962
963 if (!__cur_stmt || !__prev_stmt)
964 return;
965 if (__cur_stmt->type != STMT_ITERATOR)
966 return;
967 if (__cur_stmt->iterator_pre_condition != expr)
968 return;
969
970 /* literals are handled in smatch_extra.c */
971 if (get_value(expr->right, &sval))
972 return;
973
974 /* First time checking the condition */
975 if (__prev_stmt == __cur_stmt->iterator_pre_statement) {
976 if (!get_implied_value(expr->left, &sval) ||
977 sval.value != 0)
978 return;
979
980 iter_name = expr_to_var_sym(expr->left, &iter_sym);
981 cap_name = expr_to_var_sym(expr->right, &cap_sym);
982 if (!iter_name || !cap_name || !iter_sym || !cap_sym) {
983 free_string(iter_name);
984 free_string(cap_name);
985 return;
986 }
987
988 set_state(inc_dec_id, iter_name, iter_sym, &start);
989 store_link(inc_dec_link_id, cap_name, cap_sym, iter_name, iter_sym);
990
991 free_string(iter_name);
992 free_string(cap_name);
993 return;
994 }
995
996 /* Second time checking the condtion */
997 if (__prev_stmt != __cur_stmt->iterator_post_statement)
998 return;
999
1000 if (get_state_chunk(inc_dec_id, expr->left) != &incremented)
1001 return;
1002
1003 data = false_state->data;
1004 false_state = alloc_compare_state(
1005 data->left, data->left_var, data->left_vsl,
1006 SPECIAL_EQUAL,
1007 data->right, data->right_var, data->right_vsl);
1008
1009 set_true_false_states(compare_id, state_name, NULL, NULL, false_state);
1010 }
1011
1012 static int is_plus_one(struct expression *expr)
1013 {
1014 sval_t sval;
1015
1016 if (expr->type != EXPR_BINOP || expr->op != '+')
1017 return 0;
1018 if (!get_implied_value(expr->right, &sval) || sval.value != 1)
1019 return 0;
1020 return 1;
1021 }
1022
1023 static int is_minus_one(struct expression *expr)
1024 {
1025 sval_t sval;
1026
1027 if (expr->type != EXPR_BINOP || expr->op != '-')
1028 return 0;
1029 if (!get_implied_value(expr->right, &sval) || sval.value != 1)
1030 return 0;
1031 return 1;
1032 }
1033
1034 static void move_plus_to_minus_helper(struct expression **left_p, struct expression **right_p)
1035 {
1036 struct expression *left = *left_p;
1037 struct expression *right = *right_p;
1038
1039 /*
1040 * These two are basically equivalent: "foo + 1 != bar" and
1041 * "foo != bar - 1". There are issues with signedness and integer
1042 * overflows. There are also issues with type as well. But let's
1043 * pretend we can ignore all that stuff for now.
1044 *
1045 */
1046
1047 if (!is_plus_one(left))
1048 return;
1049
1050 *left_p = left->left;
1051 *right_p = binop_expression(right, '-', left->right);
1052 }
1053
1054 static void move_plus_to_minus(struct expression **left_p, struct expression **right_p)
1055 {
1056 if (is_plus_one(*left_p) && is_plus_one(*right_p))
1057 return;
1058
1059 move_plus_to_minus_helper(left_p, right_p);
1060 move_plus_to_minus_helper(right_p, left_p);
1061 }
1062
1063 static void handle_comparison(struct expression *left_expr, int op, struct expression *right_expr, char **_state_name, struct smatch_state **_false_state)
1064 {
1065 char *left = NULL;
1066 char *right = NULL;
1067 struct symbol *left_sym, *right_sym;
1068 struct var_sym_list *left_vsl, *right_vsl;
1069 int false_op;
1070 int orig_comparison;
1071 struct smatch_state *true_state, *false_state;
1072 static char state_name[256];
1073 struct stree *pre_stree;
1074 sval_t sval;
1075
1076 left_expr = strip_parens(left_expr);
1077 right_expr = strip_parens(right_expr);
1078
1079 false_op = negate_comparison(op);
1080
1081 move_plus_to_minus(&left_expr, &right_expr);
1082
1083 if (op == SPECIAL_UNSIGNED_LT &&
1084 get_implied_value(left_expr, &sval) &&
1085 sval.value == 0)
1086 false_op = SPECIAL_EQUAL;
1087
1088 if (op == SPECIAL_UNSIGNED_GT &&
1089 get_implied_value(right_expr, &sval) &&
1090 sval.value == 0)
1091 false_op = SPECIAL_EQUAL;
1092
1093 left = chunk_to_var_sym(left_expr, &left_sym);
1094 if (!left)
1095 goto free;
1096 left_vsl = expr_to_vsl(left_expr);
1097 right = chunk_to_var_sym(right_expr, &right_sym);
1098 if (!right)
1099 goto free;
1100 right_vsl = expr_to_vsl(right_expr);
1101
1102 if (strcmp(left, right) > 0) {
1103 struct symbol *tmp_sym = left_sym;
1104 char *tmp_name = left;
1105 struct var_sym_list *tmp_vsl = left_vsl;
1106 struct expression *tmp_expr = left_expr;
1107
1108 left = right;
1109 left_sym = right_sym;
1110 left_vsl = right_vsl;
1111 left_expr = right_expr;
1112 right = tmp_name;
1113 right_sym = tmp_sym;
1114 right_vsl = tmp_vsl;
1115 right_expr = tmp_expr;
1116 op = flip_comparison(op);
1117 false_op = flip_comparison(false_op);
1118 }
1119
1120 orig_comparison = get_comparison(left_expr, right_expr);
1121 op = filter_comparison(orig_comparison, op);
1122 false_op = filter_comparison(orig_comparison, false_op);
1123
1124 snprintf(state_name, sizeof(state_name), "%s vs %s", left, right);
1125 true_state = alloc_compare_state(
1126 left_expr, left, left_vsl,
1127 op,
1128 right_expr, right, right_vsl);
1129 false_state = alloc_compare_state(
1130 left_expr, left, left_vsl,
1131 false_op,
1132 right_expr, right, right_vsl);
1133
1134 pre_stree = clone_stree(__get_cur_stree());
1135 update_tf_data(pre_stree, left_expr, left, left_vsl, right_expr, right, right_vsl, op, false_op);
1136 free_stree(&pre_stree);
1137
1138 set_true_false_states(compare_id, state_name, NULL, true_state, false_state);
1139 __compare_param_limit_hook(left_expr, right_expr, state_name, true_state, false_state);
1140 save_link(left_expr, state_name);
1141 save_link(right_expr, state_name);
1142
1143 if (_false_state)
1144 *_false_state = false_state;
1145 if (_state_name)
1146 *_state_name = state_name;
1147 free:
1148 free_string(left);
1149 free_string(right);
1150
1151 }
1152
1153 void __comparison_match_condition(struct expression *expr)
1154 {
1155 struct expression *left, *right, *new_left, *new_right;
1156 struct smatch_state *false_state = NULL;
1157 char *state_name = NULL;
1158
1159 if (expr->type != EXPR_COMPARE)
1160 return;
1161
1162 handle_comparison(expr->left, expr->op, expr->right, &state_name, &false_state);
1163 if (false_state && state_name)
1164 handle_for_loops(expr, state_name, false_state);
1165
1166
1167 left = strip_parens(expr->left);
1168 right = strip_parens(expr->right);
1169
1170 if (left->type == EXPR_BINOP && left->op == '+') {
1171 new_left = left->left;
1172 new_right = binop_expression(right, '-', left->right);
1173 handle_comparison(new_left, expr->op, new_right, NULL, NULL);
1174
1175 new_left = left->right;
1176 new_right = binop_expression(right, '-', left->left);
1177 handle_comparison(new_left, expr->op, new_right, NULL, NULL);
1178 }
1179 }
1180
1181 static void add_comparison_var_sym(
1182 struct expression *left_expr,
1183 const char *left_name, struct var_sym_list *left_vsl,
1184 int comparison,
1185 struct expression *right_expr,
1186 const char *right_name, struct var_sym_list *right_vsl)
1187 {
1188 struct smatch_state *state;
1189 struct var_sym *vs;
1190 char state_name[256];
1191
1192 if (strcmp(left_name, right_name) > 0) {
1193 struct expression *tmp_expr = left_expr;
1194 const char *tmp_name = left_name;
1195 struct var_sym_list *tmp_vsl = left_vsl;
1196
1197 left_expr = right_expr;
1198 left_name = right_name;
1199 left_vsl = right_vsl;
1200 right_expr = tmp_expr;
1201 right_name = tmp_name;
1202 right_vsl = tmp_vsl;
1203 comparison = flip_comparison(comparison);
1204 }
1205 snprintf(state_name, sizeof(state_name), "%s vs %s", left_name, right_name);
1206 state = alloc_compare_state(
1207 left_expr, left_name, left_vsl,
1208 comparison,
1209 right_expr, right_name, right_vsl);
1210
1211 set_state(compare_id, state_name, NULL, state);
1212
1213 FOR_EACH_PTR(left_vsl, vs) {
1214 save_link_var_sym(vs->var, vs->sym, state_name);
1215 } END_FOR_EACH_PTR(vs);
1216 FOR_EACH_PTR(right_vsl, vs) {
1217 save_link_var_sym(vs->var, vs->sym, state_name);
1218 } END_FOR_EACH_PTR(vs);
1219 }
1220
1221 static void add_comparison(struct expression *left, int comparison, struct expression *right)
1222 {
1223 char *left_name = NULL;
1224 char *right_name = NULL;
1225 struct symbol *left_sym, *right_sym;
1226 struct var_sym_list *left_vsl, *right_vsl;
1227 struct smatch_state *state;
1228 char state_name[256];
1229
1230 left_name = chunk_to_var_sym(left, &left_sym);
1231 if (!left_name)
1232 goto free;
1233 left_vsl = expr_to_vsl(left);
1234 right_name = chunk_to_var_sym(right, &right_sym);
1235 if (!right_name)
1236 goto free;
1237 right_vsl = expr_to_vsl(right);
1238
1239 if (strcmp(left_name, right_name) > 0) {
1240 struct expression *tmp_expr = left;
1241 struct symbol *tmp_sym = left_sym;
1242 char *tmp_name = left_name;
1243 struct var_sym_list *tmp_vsl = left_vsl;
1244
1245 left = right;
1246 left_name = right_name;
1247 left_sym = right_sym;
1248 left_vsl = right_vsl;
1249 right = tmp_expr;
1250 right_name = tmp_name;
1251 right_sym = tmp_sym;
1252 right_vsl = tmp_vsl;
1253 comparison = flip_comparison(comparison);
1254 }
1255 snprintf(state_name, sizeof(state_name), "%s vs %s", left_name, right_name);
1256 state = alloc_compare_state(
1257 left, left_name, left_vsl,
1258 comparison,
1259 right, right_name, right_vsl);
1260
1261 set_state(compare_id, state_name, NULL, state);
1262 save_link(left, state_name);
1263 save_link(right, state_name);
1264
1265 free:
1266 free_string(left_name);
1267 free_string(right_name);
1268 }
1269
1270 static void match_assign_add(struct expression *expr)
1271 {
1272 struct expression *right;
1273 struct expression *r_left, *r_right;
1274 sval_t left_tmp, right_tmp;
1275
1276 right = strip_expr(expr->right);
1277 r_left = strip_expr(right->left);
1278 r_right = strip_expr(right->right);
1279
1280 get_absolute_min(r_left, &left_tmp);
1281 get_absolute_min(r_right, &right_tmp);
1282
1283 if (left_tmp.value > 0)
1284 add_comparison(expr->left, '>', r_right);
1285 else if (left_tmp.value == 0)
1286 add_comparison(expr->left, SPECIAL_GTE, r_right);
1287
1288 if (right_tmp.value > 0)
1289 add_comparison(expr->left, '>', r_left);
1290 else if (right_tmp.value == 0)
1291 add_comparison(expr->left, SPECIAL_GTE, r_left);
1292 }
1293
1294 static void match_assign_sub(struct expression *expr)
1295 {
1296 struct expression *right;
1297 struct expression *r_left, *r_right;
1298 int comparison;
1299 sval_t min;
1300
1301 right = strip_expr(expr->right);
1302 r_left = strip_expr(right->left);
1303 r_right = strip_expr(right->right);
1304
1305 if (get_absolute_min(r_right, &min) && sval_is_negative(min))
1306 return;
1307
1308 comparison = get_comparison(r_left, r_right);
1309
1310 switch (comparison) {
1311 case '>':
1312 case SPECIAL_GTE:
1313 if (implied_not_equal(r_right, 0))
1314 add_comparison(expr->left, '>', r_left);
1315 else
1316 add_comparison(expr->left, SPECIAL_GTE, r_left);
1317 return;
1318 }
1319 }
1320
1321 static void match_assign_divide(struct expression *expr)
1322 {
1323 struct expression *right;
1324 struct expression *r_left, *r_right;
1325 sval_t min;
1326
1327 right = strip_expr(expr->right);
1328 r_left = strip_expr(right->left);
1329 r_right = strip_expr(right->right);
1330 if (!get_implied_min(r_right, &min) || min.value <= 1)
1331 return;
1332
1333 add_comparison(expr->left, '<', r_left);
1334 }
1335
1336 static void match_binop_assign(struct expression *expr)
1337 {
1338 struct expression *right;
1339
1340 right = strip_expr(expr->right);
1341 if (right->op == '+')
1342 match_assign_add(expr);
1343 if (right->op == '-')
1344 match_assign_sub(expr);
1345 if (right->op == '/')
1346 match_assign_divide(expr);
1347 }
1348
1349 static void copy_comparisons(struct expression *left, struct expression *right)
1350 {
1351 struct string_list *links;
1352 struct smatch_state *state;
1353 struct compare_data *data;
1354 struct symbol *left_sym, *right_sym;
1355 char *left_var = NULL;
1356 char *right_var = NULL;
1357 struct var_sym_list *left_vsl;
1358 struct expression *expr;
1359 const char *var;
1360 struct var_sym_list *vsl;
1361 int comparison;
1362 char *tmp;
1363
1364 left_var = chunk_to_var_sym(left, &left_sym);
1365 if (!left_var)
1366 goto done;
1367 left_vsl = expr_to_vsl(left);
1368 right_var = chunk_to_var_sym(right, &right_sym);
1369 if (!right_var)
1370 goto done;
1371
1372 state = get_state(link_id, right_var, right_sym);
1373 if (!state)
1374 return;
1375 links = state->data;
1376
1377 FOR_EACH_PTR(links, tmp) {
1378 state = get_state(compare_id, tmp, NULL);
1379 if (!state || !state->data)
1380 continue;
1381 data = state->data;
1382 comparison = data->comparison;
1383 expr = data->right;
1384 var = data->right_var;
1385 vsl = data->right_vsl;
1386 if (strcmp(var, right_var) == 0) {
1387 expr = data->left;
1388 var = data->left_var;
1389 vsl = data->left_vsl;
1390 comparison = flip_comparison(comparison);
1391 }
1392 add_comparison_var_sym(left, left_var, left_vsl, comparison, expr, var, vsl);
1393 } END_FOR_EACH_PTR(tmp);
1394
1395 done:
1396 free_string(right_var);
1397 }
1398
1399 static void match_assign(struct expression *expr)
1400 {
1401 struct expression *right;
1402
1403 if (expr->op != '=')
1404 return;
1405 if (__in_fake_assign || outside_of_function())
1406 return;
1407
1408 if (is_struct(expr->left))
1409 return;
1410
1411 copy_comparisons(expr->left, expr->right);
1412 add_comparison(expr->left, SPECIAL_EQUAL, expr->right);
1413
1414 right = strip_expr(expr->right);
1415 if (right->type == EXPR_BINOP)
1416 match_binop_assign(expr);
1417 }
1418
1419 int get_comparison_strings(const char *one, const char *two)
1420 {
1421 char buf[256];
1422 struct smatch_state *state;
1423 int invert = 0;
1424 int ret = 0;
1425
1426 if (strcmp(one, two) == 0)
1427 return SPECIAL_EQUAL;
1428
1429 if (strcmp(one, two) > 0) {
1430 const char *tmp = one;
1431
1432 one = two;
1433 two = tmp;
1434 invert = 1;
1435 }
1436
1437 snprintf(buf, sizeof(buf), "%s vs %s", one, two);
1438 state = get_state(compare_id, buf, NULL);
1439 if (state)
1440 ret = state_to_comparison(state);
1441
1442 if (invert)
1443 ret = flip_comparison(ret);
1444
1445 return ret;
1446 }
1447
1448 int get_comparison(struct expression *a, struct expression *b)
1449 {
1450 char *one = NULL;
1451 char *two = NULL;
1452 int ret = 0;
1453
1454 a = strip_parens(a);
1455 b = strip_parens(b);
1456
1457 move_plus_to_minus(&a, &b);
1458
1459 one = chunk_to_var(a);
1460 if (!one)
1461 goto free;
1462 two = chunk_to_var(b);
1463 if (!two)
1464 goto free;
1465
1466 ret = get_comparison_strings(one, two);
1467 if (ret)
1468 goto free;
1469
1470 if (is_plus_one(a) || is_minus_one(a)) {
1471 free_string(one);
1472 one = chunk_to_var(a->left);
1473 ret = get_comparison_strings(one, two);
1474 } else if (is_plus_one(b) || is_minus_one(b)) {
1475 free_string(two);
1476 two = chunk_to_var(b->left);
1477 ret = get_comparison_strings(one, two);
1478 }
1479
1480 if (!ret)
1481 goto free;
1482
1483 if ((is_plus_one(a) || is_minus_one(b)) && ret == '<')
1484 ret = SPECIAL_LTE;
1485 else if ((is_minus_one(a) || is_plus_one(b)) && ret == '>')
1486 ret = SPECIAL_GTE;
1487 else
1488 ret = 0;
1489
1490 free:
1491 free_string(one);
1492 free_string(two);
1493 return ret;
1494 }
1495
1496 int possible_comparison(struct expression *a, int comparison, struct expression *b)
1497 {
1498 char *one = NULL;
1499 char *two = NULL;
1500 int ret = 0;
1501 char buf[256];
1502 struct sm_state *sm;
1503 int saved;
1504
1505 one = chunk_to_var(a);
1506 if (!one)
1507 goto free;
1508 two = chunk_to_var(b);
1509 if (!two)
1510 goto free;
1511
1512
1513 if (strcmp(one, two) == 0 && comparison == SPECIAL_EQUAL) {
1514 ret = 1;
1515 goto free;
1516 }
1517
1518 if (strcmp(one, two) > 0) {
1519 char *tmp = one;
1520
1521 one = two;
1522 two = tmp;
1523 comparison = flip_comparison(comparison);
1524 }
1525
1526 snprintf(buf, sizeof(buf), "%s vs %s", one, two);
1527 sm = get_sm_state(compare_id, buf, NULL);
1528 if (!sm)
1529 goto free;
1530
1531 FOR_EACH_PTR(sm->possible, sm) {
1532 if (!sm->state->data)
1533 continue;
1534 saved = ((struct compare_data *)sm->state->data)->comparison;
1535 if (saved == comparison)
1536 ret = 1;
1537 if (comparison == SPECIAL_EQUAL &&
1538 (saved == SPECIAL_LTE ||
1539 saved == SPECIAL_GTE ||
1540 saved == SPECIAL_UNSIGNED_LTE ||
1541 saved == SPECIAL_UNSIGNED_GTE))
1542 ret = 1;
1543 if (ret == 1)
1544 goto free;
1545 } END_FOR_EACH_PTR(sm);
1546
1547 return ret;
1548 free:
1549 free_string(one);
1550 free_string(two);
1551 return ret;
1552 }
1553
1554 struct state_list *get_all_comparisons(struct expression *expr)
1555 {
1556 struct smatch_state *state;
1557 struct string_list *links;
1558 struct state_list *ret = NULL;
1559 struct sm_state *sm;
1560 char *tmp;
1561
1562 state = get_state_chunk(link_id, expr);
1563 if (!state)
1564 return NULL;
1565 links = state->data;
1566
1567 FOR_EACH_PTR(links, tmp) {
1568 sm = get_sm_state(compare_id, tmp, NULL);
1569 if (!sm)
1570 continue;
1571 // FIXME have to compare name with vsl
1572 add_ptr_list(&ret, sm);
1573 } END_FOR_EACH_PTR(tmp);
1574
1575 return ret;
1576 }
1577
1578 struct state_list *get_all_possible_equal_comparisons(struct expression *expr)
1579 {
1580 struct smatch_state *state;
1581 struct string_list *links;
1582 struct state_list *ret = NULL;
1583 struct sm_state *sm;
1584 char *tmp;
1585
1586 state = get_state_chunk(link_id, expr);
1587 if (!state)
1588 return NULL;
1589 links = state->data;
1590
1591 FOR_EACH_PTR(links, tmp) {
1592 sm = get_sm_state(compare_id, tmp, NULL);
1593 if (!sm)
1594 continue;
1595 if (!strchr(sm->state->name, '='))
1596 continue;
1597 if (strcmp(sm->state->name, "!=") == 0)
1598 continue;
1599 add_ptr_list(&ret, sm);
1600 } END_FOR_EACH_PTR(tmp);
1601
1602 return ret;
1603 }
1604
1605
1606 static void update_links_from_call(struct expression *left,
1607 int left_compare,
1608 struct expression *right)
1609 {
1610 struct string_list *links;
1611 struct smatch_state *state;
1612 struct compare_data *data;
1613 struct symbol *left_sym, *right_sym;
1614 char *left_var = NULL;
1615 char *right_var = NULL;
1616 struct var_sym_list *left_vsl;
1617 struct expression *expr;
1618 const char *var;
1619 struct var_sym_list *vsl;
1620 int comparison;
1621 char *tmp;
1622
1623 left_var = chunk_to_var_sym(left, &left_sym);
1624 if (!left_var)
1625 goto done;
1626 left_vsl = expr_to_vsl(left);
1627 right_var = chunk_to_var_sym(right, &right_sym);
1628 if (!right_var)
1629 goto done;
1630
1631 state = get_state(link_id, right_var, right_sym);
1632 if (!state)
1633 return;
1634 links = state->data;
1635
1636 FOR_EACH_PTR(links, tmp) {
1637 state = get_state(compare_id, tmp, NULL);
1638 if (!state || !state->data)
1639 continue;
1640 data = state->data;
1641 comparison = data->comparison;
1642 expr = data->right;
1643 var = data->right_var;
1644 vsl = data->right_vsl;
1645 if (strcmp(var, right_var) == 0) {
1646 expr = data->left;
1647 var = data->left_var;
1648 vsl = data->left_vsl;
1649 comparison = flip_comparison(comparison);
1650 }
1651 comparison = combine_comparisons(left_compare, comparison);
1652 if (!comparison)
1653 continue;
1654 add_comparison_var_sym(left, left_var, left_vsl, comparison, expr, var, vsl);
1655 } END_FOR_EACH_PTR(tmp);
1656
1657 done:
1658 free_string(right_var);
1659 }
1660
1661 void __add_return_comparison(struct expression *call, const char *range)
1662 {
1663 struct expression *arg;
1664 int comparison;
1665 char buf[4];
1666
1667 if (!str_to_comparison_arg(range, call, &comparison, &arg))
1668 return;
1669 snprintf(buf, sizeof(buf), "%s", show_special(comparison));
1670 update_links_from_call(call, comparison, arg);
1671 add_comparison(call, comparison, arg);
1672 }
1673
1674 void __add_comparison_info(struct expression *expr, struct expression *call, const char *range)
1675 {
1676 copy_comparisons(expr, call);
1677 }
1678
1679 static char *get_mask_comparison(struct expression *expr, int ignore)
1680 {
1681 struct expression *tmp, *right;
1682 int count, param;
1683 char buf[256];
1684
1685 /* The return value for "return foo & param;" is <= param */
1686
1687 count = 0;
1688 while ((tmp = get_assigned_expr(expr))) {
1689 expr = strip_expr(tmp);
1690 if (count++ > 4)
1691 break;
1692 }
1693
1694 if (local_debug)
1695 sm_msg("%s: %s", __func__, expr_to_str(expr));
1696
1697 if (expr->type != EXPR_BINOP || expr->op != '&')
1698 return NULL;
1699
1700 right = strip_expr(expr->right);
1701 param = get_param_num(right);
1702
1703 if (param == ignore)
1704 return NULL;
1705
1706 snprintf(buf, sizeof(buf), "[<=$%d]", param);
1707 return alloc_sname(buf);
1708 }
1709
1710 static char *range_comparison_to_param_helper(struct expression *expr, char starts_with, int ignore)
1711 {
1712 struct symbol *param;
1713 char *var = NULL;
1714 char buf[256];
1715 char *ret_str = NULL;
1716 int compare;
1717 int i;
1718
1719 if (!expr)
1720 return NULL;
1721
1722 var = chunk_to_var(expr);
1723 if (!var)
1724 goto try_mask;
1725
1726 i = -1;
1727 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
1728 i++;
1729 if (i == ignore)
1730 continue;
1731 if (!param->ident)
1732 continue;
1733 snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
1734 compare = get_comparison_strings(var, buf);
1735 if (!compare)
1736 continue;
1737 if (show_special(compare)[0] != starts_with)
1738 continue;
1739 snprintf(buf, sizeof(buf), "[%s$%d]", show_special(compare), i);
1740 ret_str = alloc_sname(buf);
1741 break;
1742 } END_FOR_EACH_PTR(param);
1743
1744 free_string(var);
1745 if (!ret_str)
1746 goto try_mask;
1747
1748 return ret_str;
1749
1750 try_mask:
1751 if (starts_with == '<')
1752 ret_str = get_mask_comparison(expr, ignore);
1753 return ret_str;
1754 }
1755
1756 char *name_sym_to_param_comparison(const char *name, struct symbol *sym)
1757 {
1758 struct symbol *param;
1759 char buf[256];
1760 int compare;
1761 int i;
1762
1763 i = -1;
1764 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
1765 i++;
1766 if (!param->ident)
1767 continue;
1768 snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
1769 compare = get_comparison_strings(name, buf);
1770 if (!compare)
1771 continue;
1772 snprintf(buf, sizeof(buf), "[%s$%d]", show_special(compare), i);
1773 return alloc_sname(buf);
1774 } END_FOR_EACH_PTR(param);
1775
1776 return NULL;
1777 }
1778
1779 char *expr_equal_to_param(struct expression *expr, int ignore)
1780 {
1781 return range_comparison_to_param_helper(expr, '=', ignore);
1782 }
1783
1784 char *expr_lte_to_param(struct expression *expr, int ignore)
1785 {
1786 return range_comparison_to_param_helper(expr, '<', ignore);
1787 }
1788
1789 char *expr_param_comparison(struct expression *expr, int ignore)
1790 {
1791 struct symbol *param;
1792 char *var = NULL;
1793 char buf[256];
1794 char *ret_str = NULL;
1795 int compare;
1796 int i;
1797
1798 var = chunk_to_var(expr);
1799 if (!var)
1800 goto free;
1801
1802 i = -1;
1803 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
1804 i++;
1805 if (i == ignore)
1806 continue;
1807 if (!param->ident)
1808 continue;
1809 snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
1810 compare = get_comparison_strings(var, buf);
1811 if (!compare)
1812 continue;
1813 snprintf(buf, sizeof(buf), "[%s$%d]", show_special(compare), i);
1814 ret_str = alloc_sname(buf);
1815 break;
1816 } END_FOR_EACH_PTR(param);
1817
1818 free:
1819 free_string(var);
1820 return ret_str;
1821 }
1822
1823 char *get_printed_param_name(struct expression *call, const char *param_name, struct symbol *param_sym)
1824 {
1825 struct expression *arg;
1826 char *name;
1827 struct symbol *sym;
1828 static char buf[256];
1829 int len;
1830 int i;
1831
1832 i = -1;
1833 FOR_EACH_PTR(call->args, arg) {
1834 i++;
1835
1836 name = expr_to_var_sym(arg, &sym);
1837 if (!name || !sym)
1838 continue;
1839 if (sym != param_sym)
1840 continue;
1841
1842 len = strlen(name);
1843 if (strncmp(name, param_name, len) != 0)
1844 continue;
1845 if (param_name[len] == '\0') {
1846 snprintf(buf, sizeof(buf), "$%d", i);
1847 return buf;
1848 }
1849 if (param_name[len] != '-')
1850 continue;
1851 snprintf(buf, sizeof(buf), "$%d%s", i, param_name + len);
1852 return buf;
1853 } END_FOR_EACH_PTR(arg);
1854
1855 return NULL;
1856 }
1857
1858 static void match_call_info(struct expression *expr)
1859 {
1860 struct expression *arg;
1861 struct smatch_state *state;
1862 struct sm_state *sm;
1863 struct compare_data *data;
1864 int comparison;
1865 struct string_list *links;
1866 char *arg_name;
1867 const char *right_name;
1868 char *link;
1869 char info_buf[256];
1870 int i;
1871
1872 i = -1;
1873 FOR_EACH_PTR(expr->args, arg) {
1874 i++;
1875
1876 state = get_state_chunk(link_id, arg);
1877 if (!state)
1878 continue;
1879
1880 links = state->data;
1881 FOR_EACH_PTR(links, link) {
1882 struct var_sym_list *right_vsl;
1883 struct var_sym *right_vs;
1884
1885
1886 if (strstr(link, " orig"))
1887 continue;
1888 sm = get_sm_state(compare_id, link, NULL);
1889 if (!sm)
1890 continue;
1891 data = sm->state->data;
1892 if (!data || !data->comparison)
1893 continue;
1894 arg_name = expr_to_var(arg);
1895 if (!arg_name)
1896 continue;
1897
1898 right_vsl = NULL;
1899 if (strcmp(data->left_var, arg_name) == 0) {
1900 comparison = data->comparison;
1901 right_name = data->right_var;
1902 right_vsl = data->right_vsl;
1903 } else if (strcmp(data->right_var, arg_name) == 0) {
1904 comparison = flip_comparison(data->comparison);
1905 right_name = data->left_var;
1906 right_vsl = data->left_vsl;
1907 }
1908 if (!right_vsl || ptr_list_size((struct ptr_list *)right_vsl) != 1)
1909 goto free;
1910
1911 right_vs = first_ptr_list((struct ptr_list *)right_vsl);
1912 if (strcmp(right_vs->var, right_name) != 0)
1913 goto free;
1914 right_name = get_printed_param_name(expr, right_vs->var, right_vs->sym);
1915 if (!right_name)
1916 goto free;
1917 snprintf(info_buf, sizeof(info_buf), "%s %s", show_special(comparison), right_name);
1918 sql_insert_caller_info(expr, PARAM_COMPARE, i, "$", info_buf);
1919
1920 free:
1921 free_string(arg_name);
1922 } END_FOR_EACH_PTR(link);
1923 } END_FOR_EACH_PTR(arg);
1924 }
1925
1926 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *link_sm)
1927 {
1928 struct sm_state *compare_sm;
1929 struct string_list *links;
1930 char *link;
1931 struct compare_data *data;
1932 struct var_sym *left, *right;
1933 static char info_buf[256];
1934 const char *right_name;
1935
1936 if (strstr(printed_name, " orig"))
1937 return;
1938
1939 links = link_sm->state->data;
1940 FOR_EACH_PTR(links, link) {
1941 compare_sm = get_sm_state(compare_id, link, NULL);
1942 if (!compare_sm)
1943 continue;
1944 data = compare_sm->state->data;
1945 if (!data || !data->comparison)
1946 continue;
1947
1948 if (ptr_list_size((struct ptr_list *)data->left_vsl) != 1 ||
1949 ptr_list_size((struct ptr_list *)data->right_vsl) != 1)
1950 continue;
1951 left = first_ptr_list((struct ptr_list *)data->left_vsl);
1952 right = first_ptr_list((struct ptr_list *)data->right_vsl);
1953 if (left->sym == right->sym &&
1954 strcmp(left->var, right->var) == 0)
1955 continue;
1956 /*
1957 * Both parameters link to this comparison so only
1958 * record the first one.
1959 */
1960 if (left->sym != link_sm->sym ||
1961 strcmp(left->var, link_sm->name) != 0)
1962 continue;
1963
1964 right_name = get_printed_param_name(call, right->var, right->sym);
1965 if (!right_name)
1966 continue;
1967 snprintf(info_buf, sizeof(info_buf), "%s %s", show_special(data->comparison), right_name);
1968 sql_insert_caller_info(call, PARAM_COMPARE, param, printed_name, info_buf);
1969 } END_FOR_EACH_PTR(link);
1970 }
1971
1972 static void print_return_value_comparison(int return_id, char *return_ranges, struct expression *expr)
1973 {
1974 char *name;
1975 const char *tmp_name;
1976 struct symbol *sym;
1977 int param;
1978 char info_buf[256];
1979
1980 /*
1981 * TODO: This only prints == comparisons. That's probably the most
1982 * useful comparison because == max has lots of implications. But it
1983 * would be good to capture the rest as well.
1984 *
1985 * This information is already in the DB but it's in the parameter math
1986 * bits and it's awkward to use it. This is is the simpler, possibly
1987 * cleaner way, but not necessarily the best, I don't know.
1988 */
1989
1990 if (!expr)
1991 return;
1992 name = expr_to_var_sym(expr, &sym);
1993 if (!name || !sym)
1994 goto free;
1995
1996 param = get_param_num_from_sym(sym);
1997 if (param < 0)
1998 goto free;
1999 if (param_was_set_var_sym(name, sym))
2000 goto free;
2001
2002 tmp_name = get_param_name_var_sym(name, sym);
2003 if (!tmp_name)
2004 goto free;
2005
2006 snprintf(info_buf, sizeof(info_buf), "== $%d%s", param, tmp_name + 1);
2007 sql_insert_return_states(return_id, return_ranges,
2008 PARAM_COMPARE, -1, "$", info_buf);
2009 free:
2010 free_string(name);
2011 }
2012
2013 static void print_return_comparison(int return_id, char *return_ranges, struct expression *expr)
2014 {
2015 struct sm_state *tmp;
2016 struct string_list *links;
2017 char *link;
2018 struct sm_state *sm;
2019 struct compare_data *data;
2020 struct var_sym *left, *right;
2021 int left_param, right_param;
2022 char left_buf[256];
2023 char right_buf[256];
2024 char info_buf[256];
2025 const char *tmp_name;
2026
2027 print_return_value_comparison(return_id, return_ranges, expr);
2028
2029 FOR_EACH_MY_SM(link_id, __get_cur_stree(), tmp) {
2030 if (get_param_num_from_sym(tmp->sym) < 0)
2031 continue;
2032 links = tmp->state->data;
2033 FOR_EACH_PTR(links, link) {
2034 sm = get_sm_state(compare_id, link, NULL);
2035 if (!sm)
2036 continue;
2037 data = sm->state->data;
2038 if (!data || !data->comparison)
2039 continue;
2040 if (ptr_list_size((struct ptr_list *)data->left_vsl) != 1 ||
2041 ptr_list_size((struct ptr_list *)data->right_vsl) != 1)
2042 continue;
2043 left = first_ptr_list((struct ptr_list *)data->left_vsl);
2044 right = first_ptr_list((struct ptr_list *)data->right_vsl);
2045 if (left->sym == right->sym &&
2046 strcmp(left->var, right->var) == 0)
2047 continue;
2048 /*
2049 * Both parameters link to this comparison so only
2050 * record the first one.
2051 */
2052 if (left->sym != tmp->sym ||
2053 strcmp(left->var, tmp->name) != 0)
2054 continue;
2055
2056 if (strstr(right->var, " orig"))
2057 continue;
2058
2059 left_param = get_param_num_from_sym(left->sym);
2060 right_param = get_param_num_from_sym(right->sym);
2061 if (left_param < 0 || right_param < 0)
2062 continue;
2063
2064 tmp_name = get_param_name_var_sym(left->var, left->sym);
2065 if (!tmp_name)
2066 continue;
2067 snprintf(left_buf, sizeof(left_buf), "%s", tmp_name);
2068
2069 tmp_name = get_param_name_var_sym(right->var, right->sym);
2070 if (!tmp_name || tmp_name[0] != '$')
2071 continue;
2072 snprintf(right_buf, sizeof(right_buf), "$%d%s", right_param, tmp_name + 1);
2073
2074 /*
2075 * FIXME: this should reject $ type variables (as
2076 * opposed to $->foo type). Those should come from
2077 * smatch_param_compare_limit.c.
2078 */
2079
2080 snprintf(info_buf, sizeof(info_buf), "%s %s", show_special(data->comparison), right_buf);
2081 sql_insert_return_states(return_id, return_ranges,
2082 PARAM_COMPARE, left_param, left_buf, info_buf);
2083 } END_FOR_EACH_PTR(link);
2084
2085 } END_FOR_EACH_SM(tmp);
2086 }
2087
2088 static int parse_comparison(char **value, int *op)
2089 {
2090
2091 *op = **value;
2092
2093 switch (*op) {
2094 case '<':
2095 (*value)++;
2096 if (**value == '=') {
2097 (*value)++;
2098 *op = SPECIAL_LTE;
2099 }
2100 break;
2101 case '=':
2102 (*value)++;
2103 (*value)++;
2104 *op = SPECIAL_EQUAL;
2105 break;
2106 case '!':
2107 (*value)++;
2108 (*value)++;
2109 *op = SPECIAL_NOTEQUAL;
2110 break;
2111 case '>':
2112 (*value)++;
2113 if (**value == '=') {
2114 (*value)++;
2115 *op = SPECIAL_GTE;
2116 }
2117 break;
2118 default:
2119 return 0;
2120 }
2121
2122 if (**value != ' ') {
2123 sm_msg("internal error parsing comparison. %s", *value);
2124 return 0;
2125 }
2126
2127 (*value)++;
2128 return 1;
2129 }
2130
2131 static int split_op_param_key(char *value, int *op, int *param, char **key)
2132 {
2133 static char buf[256];
2134 char *p;
2135
2136 if (!parse_comparison(&value, op))
2137 return 0;
2138
2139 snprintf(buf, sizeof(buf), value);
2140
2141 p = buf;
2142 if (*p++ != '$')
2143 return 0;
2144
2145 *param = atoi(p);
2146 if (*param < 0 || *param > 99)
2147 return 0;
2148 p++;
2149 if (*param > 9)
2150 p++;
2151 p--;
2152 *p = '$';
2153 *key = p;
2154
2155 return 1;
2156 }
2157
2158 static void db_return_comparison(struct expression *expr, int left_param, char *key, char *value)
2159 {
2160 struct expression *left_arg, *right_arg;
2161 char *left_name = NULL;
2162 struct symbol *left_sym;
2163 char *right_name = NULL;
2164 struct symbol *right_sym;
2165 int op;
2166 int right_param;
2167 char *right_key;
2168 struct var_sym_list *left_vsl = NULL, *right_vsl = NULL;
2169
2170 if (left_param == -1) {
2171 if (expr->type != EXPR_ASSIGNMENT)
2172 return;
2173 left_arg = strip_expr(expr->left);
2174
2175 while (expr->type == EXPR_ASSIGNMENT)
2176 expr = strip_expr(expr->right);
2177 if (expr->type != EXPR_CALL)
2178 return;
2179 } else {
2180 while (expr->type == EXPR_ASSIGNMENT)
2181 expr = strip_expr(expr->right);
2182 if (expr->type != EXPR_CALL)
2183 return;
2184
2185 left_arg = get_argument_from_call_expr(expr->args, left_param);
2186 if (!left_arg)
2187 return;
2188 }
2189
2190 if (!split_op_param_key(value, &op, &right_param, &right_key))
2191 return;
2192
2193 right_arg = get_argument_from_call_expr(expr->args, right_param);
2194 if (!right_arg)
2195 return;
2196
2197 left_name = get_variable_from_key(left_arg, key, &left_sym);
2198 if (!left_name || !left_sym)
2199 goto free;
2200
2201 right_name = get_variable_from_key(right_arg, right_key, &right_sym);
2202 if (!right_name || !right_sym)
2203 goto free;
2204
2205 add_var_sym(&left_vsl, left_name, left_sym);
2206 add_var_sym(&right_vsl, right_name, right_sym);
2207
2208 add_comparison_var_sym(NULL, left_name, left_vsl, op, NULL, right_name, right_vsl);
2209
2210 free:
2211 free_string(left_name);
2212 free_string(right_name);
2213 }
2214
2215 int param_compare_limit_is_impossible(struct expression *expr, int left_param, char *left_key, char *value)
2216 {
2217 struct smatch_state *state;
2218 char *left_name = NULL;
2219 char *right_name = NULL;
2220 struct symbol *left_sym, *right_sym;
2221 struct expression *left_arg, *right_arg;
2222 int op, state_op;
2223 int right_param;
2224 char *right_key;
2225 int ret = 0;
2226 char buf[256];
2227
2228 while (expr->type == EXPR_ASSIGNMENT)
2229 expr = strip_expr(expr->right);
2230 if (expr->type != EXPR_CALL)
2231 return 0;
2232
2233 if (!split_op_param_key(value, &op, &right_param, &right_key))
2234 return 0;
2235
2236 left_arg = get_argument_from_call_expr(expr->args, left_param);
2237 if (!left_arg)
2238 return 0;
2239
2240 right_arg = get_argument_from_call_expr(expr->args, right_param);
2241 if (!right_arg)
2242 return 0;
2243
2244 left_name = get_variable_from_key(left_arg, left_key, &left_sym);
2245 right_name = get_variable_from_key(right_arg, right_key, &right_sym);
2246 if (!left_name || !right_name)
2247 goto free;
2248
2249 snprintf(buf, sizeof(buf), "%s vs %s", left_name, right_name);
2250 state = get_state(compare_id, buf, NULL);
2251 if (!state)
2252 goto free;
2253 state_op = state_to_comparison(state);
2254 if (!state_op)
2255 goto free;
2256
2257 if (!filter_comparison(remove_unsigned_from_comparison(state_op), op))
2258 ret = 1;
2259 free:
2260 free_string(left_name);
2261 free_string(right_name);
2262 return ret;
2263 }
2264
2265 static void free_data(struct symbol *sym)
2266 {
2267 if (__inline_fn)
2268 return;
2269 clear_compare_data_alloc();
2270 }
2271
2272 void register_comparison(int id)
2273 {
2274 compare_id = id;
2275 add_hook(&save_start_states, AFTER_DEF_HOOK);
2276 add_unmatched_state_hook(compare_id, unmatched_comparison);
2277 add_merge_hook(compare_id, &merge_compare_states);
2278 add_hook(&free_data, AFTER_FUNC_HOOK);
2279 add_hook(&match_call_info, FUNCTION_CALL_HOOK);
2280 add_split_return_callback(&print_return_comparison);
2281
2282 select_return_states_hook(PARAM_COMPARE, &db_return_comparison);
2283 }
2284
2285 void register_comparison_late(int id)
2286 {
2287 add_hook(&match_assign, ASSIGNMENT_HOOK);
2288 }
2289
2290 void register_comparison_links(int id)
2291 {
2292 link_id = id;
2293 add_merge_hook(link_id, &merge_links);
2294 add_modification_hook(link_id, &match_modify);
2295
2296 add_member_info_callback(link_id, struct_member_callback);
2297 }
2298
2299 void register_comparison_inc_dec(int id)
2300 {
2301 inc_dec_id = id;
2302 add_modification_hook_late(inc_dec_id, &iter_modify);
2303 }
2304
2305 void register_comparison_inc_dec_links(int id)
2306 {
2307 inc_dec_link_id = id;
2308 set_up_link_functions(inc_dec_id, inc_dec_link_id);
2309 }
2310
2311 static void filter_by_sm(struct sm_state *sm, int op,
2312 struct state_list **true_stack,
2313 struct state_list **false_stack)
2314 {
2315 struct compare_data *data;
2316 int istrue = 0;
2317 int isfalse = 0;
2318
2319 if (!sm)
2320 return;
2321 data = sm->state->data;
2322 if (!data) {
2323 if (sm->merged) {
2324 filter_by_sm(sm->left, op, true_stack, false_stack);
2325 filter_by_sm(sm->right, op, true_stack, false_stack);
2326 }
2327 return;
2328 }
2329
2330 if (data->comparison &&
2331 data->comparison == filter_comparison(data->comparison, op))
2332 istrue = 1;
2333
2334 if (data->comparison &&
2335 data->comparison == filter_comparison(data->comparison, negate_comparison(op)))
2336 isfalse = 1;
2337
2338 if (istrue)
2339 add_ptr_list(true_stack, sm);
2340 if (isfalse)
2341 add_ptr_list(false_stack, sm);
2342
2343 if (sm->merged) {
2344 filter_by_sm(sm->left, op, true_stack, false_stack);
2345 filter_by_sm(sm->right, op, true_stack, false_stack);
2346 }
2347 }
2348
2349 struct sm_state *comparison_implication_hook(struct expression *expr,
2350 struct state_list **true_stack,
2351 struct state_list **false_stack)
2352 {
2353 struct sm_state *sm;
2354 char *left, *right;
2355 int op;
2356 static char buf[256];
2357
2358 if (expr->type != EXPR_COMPARE)
2359 return NULL;
2360
2361 op = expr->op;
2362
2363 left = expr_to_var(expr->left);
2364 right = expr_to_var(expr->right);
2365 if (!left || !right) {
2366 free_string(left);
2367 free_string(right);
2368 return NULL;
2369 }
2370
2371 if (strcmp(left, right) > 0) {
2372 char *tmp = left;
2373
2374 left = right;
2375 right = tmp;
2376 op = flip_comparison(op);
2377 }
2378
2379 snprintf(buf, sizeof(buf), "%s vs %s", left, right);
2380 sm = get_sm_state(compare_id, buf, NULL);
2381 if (!sm)
2382 return NULL;
2383 if (!sm->merged)
2384 return NULL;
2385
2386 filter_by_sm(sm, op, true_stack, false_stack);
2387 if (!*true_stack && !*false_stack)
2388 return NULL;
2389
2390 return sm;
2391 }
Static analysis for C