?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
symbol.h: let is_ptr_type() take NULL pointers
[smatch.git] / smatch_comparison.c
blobc4b1f78b07ae9e30fe6e39ddd95982bc2f75e989
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 (!one || !two)
1427 return 0;
1428
1429 if (strcmp(one, two) == 0)
1430 return SPECIAL_EQUAL;
1431
1432 if (strcmp(one, two) > 0) {
1433 const char *tmp = one;
1434
1435 one = two;
1436 two = tmp;
1437 invert = 1;
1438 }
1439
1440 snprintf(buf, sizeof(buf), "%s vs %s", one, two);
1441 state = get_state(compare_id, buf, NULL);
1442 if (state)
1443 ret = state_to_comparison(state);
1444
1445 if (invert)
1446 ret = flip_comparison(ret);
1447
1448 return ret;
1449 }
1450
1451 int get_comparison(struct expression *a, struct expression *b)
1452 {
1453 char *one = NULL;
1454 char *two = NULL;
1455 int ret = 0;
1456
1457 a = strip_parens(a);
1458 b = strip_parens(b);
1459
1460 move_plus_to_minus(&a, &b);
1461
1462 one = chunk_to_var(a);
1463 if (!one)
1464 goto free;
1465 two = chunk_to_var(b);
1466 if (!two)
1467 goto free;
1468
1469 ret = get_comparison_strings(one, two);
1470 if (ret)
1471 goto free;
1472
1473 if (is_plus_one(a) || is_minus_one(a)) {
1474 free_string(one);
1475 one = chunk_to_var(a->left);
1476 ret = get_comparison_strings(one, two);
1477 } else if (is_plus_one(b) || is_minus_one(b)) {
1478 free_string(two);
1479 two = chunk_to_var(b->left);
1480 ret = get_comparison_strings(one, two);
1481 }
1482
1483 if (!ret)
1484 goto free;
1485
1486 if ((is_plus_one(a) || is_minus_one(b)) && ret == '<')
1487 ret = SPECIAL_LTE;
1488 else if ((is_minus_one(a) || is_plus_one(b)) && ret == '>')
1489 ret = SPECIAL_GTE;
1490 else
1491 ret = 0;
1492
1493 free:
1494 free_string(one);
1495 free_string(two);
1496 return ret;
1497 }
1498
1499 int possible_comparison(struct expression *a, int comparison, struct expression *b)
1500 {
1501 char *one = NULL;
1502 char *two = NULL;
1503 int ret = 0;
1504 char buf[256];
1505 struct sm_state *sm;
1506 int saved;
1507
1508 one = chunk_to_var(a);
1509 if (!one)
1510 goto free;
1511 two = chunk_to_var(b);
1512 if (!two)
1513 goto free;
1514
1515
1516 if (strcmp(one, two) == 0 && comparison == SPECIAL_EQUAL) {
1517 ret = 1;
1518 goto free;
1519 }
1520
1521 if (strcmp(one, two) > 0) {
1522 char *tmp = one;
1523
1524 one = two;
1525 two = tmp;
1526 comparison = flip_comparison(comparison);
1527 }
1528
1529 snprintf(buf, sizeof(buf), "%s vs %s", one, two);
1530 sm = get_sm_state(compare_id, buf, NULL);
1531 if (!sm)
1532 goto free;
1533
1534 FOR_EACH_PTR(sm->possible, sm) {
1535 if (!sm->state->data)
1536 continue;
1537 saved = ((struct compare_data *)sm->state->data)->comparison;
1538 if (saved == comparison)
1539 ret = 1;
1540 if (comparison == SPECIAL_EQUAL &&
1541 (saved == SPECIAL_LTE ||
1542 saved == SPECIAL_GTE ||
1543 saved == SPECIAL_UNSIGNED_LTE ||
1544 saved == SPECIAL_UNSIGNED_GTE))
1545 ret = 1;
1546 if (ret == 1)
1547 goto free;
1548 } END_FOR_EACH_PTR(sm);
1549
1550 return ret;
1551 free:
1552 free_string(one);
1553 free_string(two);
1554 return ret;
1555 }
1556
1557 struct state_list *get_all_comparisons(struct expression *expr)
1558 {
1559 struct smatch_state *state;
1560 struct string_list *links;
1561 struct state_list *ret = NULL;
1562 struct sm_state *sm;
1563 char *tmp;
1564
1565 state = get_state_chunk(link_id, expr);
1566 if (!state)
1567 return NULL;
1568 links = state->data;
1569
1570 FOR_EACH_PTR(links, tmp) {
1571 sm = get_sm_state(compare_id, tmp, NULL);
1572 if (!sm)
1573 continue;
1574 // FIXME have to compare name with vsl
1575 add_ptr_list(&ret, sm);
1576 } END_FOR_EACH_PTR(tmp);
1577
1578 return ret;
1579 }
1580
1581 struct state_list *get_all_possible_equal_comparisons(struct expression *expr)
1582 {
1583 struct smatch_state *state;
1584 struct string_list *links;
1585 struct state_list *ret = NULL;
1586 struct sm_state *sm;
1587 char *tmp;
1588
1589 state = get_state_chunk(link_id, expr);
1590 if (!state)
1591 return NULL;
1592 links = state->data;
1593
1594 FOR_EACH_PTR(links, tmp) {
1595 sm = get_sm_state(compare_id, tmp, NULL);
1596 if (!sm)
1597 continue;
1598 if (!strchr(sm->state->name, '='))
1599 continue;
1600 if (strcmp(sm->state->name, "!=") == 0)
1601 continue;
1602 add_ptr_list(&ret, sm);
1603 } END_FOR_EACH_PTR(tmp);
1604
1605 return ret;
1606 }
1607
1608
1609 static void update_links_from_call(struct expression *left,
1610 int left_compare,
1611 struct expression *right)
1612 {
1613 struct string_list *links;
1614 struct smatch_state *state;
1615 struct compare_data *data;
1616 struct symbol *left_sym, *right_sym;
1617 char *left_var = NULL;
1618 char *right_var = NULL;
1619 struct var_sym_list *left_vsl;
1620 struct expression *expr;
1621 const char *var;
1622 struct var_sym_list *vsl;
1623 int comparison;
1624 char *tmp;
1625
1626 left_var = chunk_to_var_sym(left, &left_sym);
1627 if (!left_var)
1628 goto done;
1629 left_vsl = expr_to_vsl(left);
1630 right_var = chunk_to_var_sym(right, &right_sym);
1631 if (!right_var)
1632 goto done;
1633
1634 state = get_state(link_id, right_var, right_sym);
1635 if (!state)
1636 return;
1637 links = state->data;
1638
1639 FOR_EACH_PTR(links, tmp) {
1640 state = get_state(compare_id, tmp, NULL);
1641 if (!state || !state->data)
1642 continue;
1643 data = state->data;
1644 comparison = data->comparison;
1645 expr = data->right;
1646 var = data->right_var;
1647 vsl = data->right_vsl;
1648 if (strcmp(var, right_var) == 0) {
1649 expr = data->left;
1650 var = data->left_var;
1651 vsl = data->left_vsl;
1652 comparison = flip_comparison(comparison);
1653 }
1654 comparison = combine_comparisons(left_compare, comparison);
1655 if (!comparison)
1656 continue;
1657 add_comparison_var_sym(left, left_var, left_vsl, comparison, expr, var, vsl);
1658 } END_FOR_EACH_PTR(tmp);
1659
1660 done:
1661 free_string(right_var);
1662 }
1663
1664 void __add_return_comparison(struct expression *call, const char *range)
1665 {
1666 struct expression *arg;
1667 int comparison;
1668 char buf[4];
1669
1670 if (!str_to_comparison_arg(range, call, &comparison, &arg))
1671 return;
1672 snprintf(buf, sizeof(buf), "%s", show_special(comparison));
1673 update_links_from_call(call, comparison, arg);
1674 add_comparison(call, comparison, arg);
1675 }
1676
1677 void __add_comparison_info(struct expression *expr, struct expression *call, const char *range)
1678 {
1679 copy_comparisons(expr, call);
1680 }
1681
1682 static char *get_mask_comparison(struct expression *expr, int ignore)
1683 {
1684 struct expression *tmp, *right;
1685 int count, param;
1686 char buf[256];
1687
1688 /* The return value for "return foo & param;" is <= param */
1689
1690 count = 0;
1691 while ((tmp = get_assigned_expr(expr))) {
1692 expr = strip_expr(tmp);
1693 if (count++ > 4)
1694 break;
1695 }
1696
1697 if (local_debug)
1698 sm_msg("%s: %s", __func__, expr_to_str(expr));
1699
1700 if (expr->type != EXPR_BINOP || expr->op != '&')
1701 return NULL;
1702
1703 right = strip_expr(expr->right);
1704 param = get_param_num(right);
1705
1706 if (param == ignore)
1707 return NULL;
1708
1709 snprintf(buf, sizeof(buf), "[<=$%d]", param);
1710 return alloc_sname(buf);
1711 }
1712
1713 static char *range_comparison_to_param_helper(struct expression *expr, char starts_with, int ignore)
1714 {
1715 struct symbol *param;
1716 char *var = NULL;
1717 char buf[256];
1718 char *ret_str = NULL;
1719 int compare;
1720 int i;
1721
1722 if (!expr)
1723 return NULL;
1724
1725 var = chunk_to_var(expr);
1726 if (!var)
1727 goto try_mask;
1728
1729 i = -1;
1730 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
1731 i++;
1732 if (i == ignore)
1733 continue;
1734 if (!param->ident)
1735 continue;
1736 snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
1737 compare = get_comparison_strings(var, buf);
1738 if (!compare)
1739 continue;
1740 if (show_special(compare)[0] != starts_with)
1741 continue;
1742 snprintf(buf, sizeof(buf), "[%s$%d]", show_special(compare), i);
1743 ret_str = alloc_sname(buf);
1744 break;
1745 } END_FOR_EACH_PTR(param);
1746
1747 free_string(var);
1748 if (!ret_str)
1749 goto try_mask;
1750
1751 return ret_str;
1752
1753 try_mask:
1754 if (starts_with == '<')
1755 ret_str = get_mask_comparison(expr, ignore);
1756 return ret_str;
1757 }
1758
1759 char *name_sym_to_param_comparison(const char *name, struct symbol *sym)
1760 {
1761 struct symbol *param;
1762 char buf[256];
1763 int compare;
1764 int i;
1765
1766 i = -1;
1767 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
1768 i++;
1769 if (!param->ident)
1770 continue;
1771 snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
1772 compare = get_comparison_strings(name, buf);
1773 if (!compare)
1774 continue;
1775 snprintf(buf, sizeof(buf), "[%s$%d]", show_special(compare), i);
1776 return alloc_sname(buf);
1777 } END_FOR_EACH_PTR(param);
1778
1779 return NULL;
1780 }
1781
1782 char *expr_equal_to_param(struct expression *expr, int ignore)
1783 {
1784 return range_comparison_to_param_helper(expr, '=', ignore);
1785 }
1786
1787 char *expr_lte_to_param(struct expression *expr, int ignore)
1788 {
1789 return range_comparison_to_param_helper(expr, '<', ignore);
1790 }
1791
1792 char *expr_param_comparison(struct expression *expr, int ignore)
1793 {
1794 struct symbol *param;
1795 char *var = NULL;
1796 char buf[256];
1797 char *ret_str = NULL;
1798 int compare;
1799 int i;
1800
1801 var = chunk_to_var(expr);
1802 if (!var)
1803 goto free;
1804
1805 i = -1;
1806 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
1807 i++;
1808 if (i == ignore)
1809 continue;
1810 if (!param->ident)
1811 continue;
1812 snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
1813 compare = get_comparison_strings(var, buf);
1814 if (!compare)
1815 continue;
1816 snprintf(buf, sizeof(buf), "[%s$%d]", show_special(compare), i);
1817 ret_str = alloc_sname(buf);
1818 break;
1819 } END_FOR_EACH_PTR(param);
1820
1821 free:
1822 free_string(var);
1823 return ret_str;
1824 }
1825
1826 char *get_printed_param_name(struct expression *call, const char *param_name, struct symbol *param_sym)
1827 {
1828 struct expression *arg;
1829 char *name;
1830 struct symbol *sym;
1831 static char buf[256];
1832 int len;
1833 int i;
1834
1835 i = -1;
1836 FOR_EACH_PTR(call->args, arg) {
1837 i++;
1838
1839 name = expr_to_var_sym(arg, &sym);
1840 if (!name || !sym)
1841 continue;
1842 if (sym != param_sym)
1843 continue;
1844
1845 len = strlen(name);
1846 if (strncmp(name, param_name, len) != 0)
1847 continue;
1848 if (param_name[len] == '\0') {
1849 snprintf(buf, sizeof(buf), "$%d", i);
1850 return buf;
1851 }
1852 if (param_name[len] != '-')
1853 continue;
1854 snprintf(buf, sizeof(buf), "$%d%s", i, param_name + len);
1855 return buf;
1856 } END_FOR_EACH_PTR(arg);
1857
1858 return NULL;
1859 }
1860
1861 static void match_call_info(struct expression *expr)
1862 {
1863 struct expression *arg;
1864 struct smatch_state *state;
1865 struct sm_state *sm;
1866 struct compare_data *data;
1867 int comparison;
1868 struct string_list *links;
1869 char *arg_name;
1870 const char *right_name;
1871 char *link;
1872 char info_buf[256];
1873 int i;
1874
1875 i = -1;
1876 FOR_EACH_PTR(expr->args, arg) {
1877 i++;
1878
1879 state = get_state_chunk(link_id, arg);
1880 if (!state)
1881 continue;
1882
1883 links = state->data;
1884 FOR_EACH_PTR(links, link) {
1885 struct var_sym_list *right_vsl;
1886 struct var_sym *right_vs;
1887
1888
1889 if (strstr(link, " orig"))
1890 continue;
1891 sm = get_sm_state(compare_id, link, NULL);
1892 if (!sm)
1893 continue;
1894 data = sm->state->data;
1895 if (!data || !data->comparison)
1896 continue;
1897 arg_name = expr_to_var(arg);
1898 if (!arg_name)
1899 continue;
1900
1901 right_vsl = NULL;
1902 if (strcmp(data->left_var, arg_name) == 0) {
1903 comparison = data->comparison;
1904 right_name = data->right_var;
1905 right_vsl = data->right_vsl;
1906 } else if (strcmp(data->right_var, arg_name) == 0) {
1907 comparison = flip_comparison(data->comparison);
1908 right_name = data->left_var;
1909 right_vsl = data->left_vsl;
1910 }
1911 if (!right_vsl || ptr_list_size((struct ptr_list *)right_vsl) != 1)
1912 goto free;
1913
1914 right_vs = first_ptr_list((struct ptr_list *)right_vsl);
1915 if (strcmp(right_vs->var, right_name) != 0)
1916 goto free;
1917 right_name = get_printed_param_name(expr, right_vs->var, right_vs->sym);
1918 if (!right_name)
1919 goto free;
1920 snprintf(info_buf, sizeof(info_buf), "%s %s", show_special(comparison), right_name);
1921 sql_insert_caller_info(expr, PARAM_COMPARE, i, "$", info_buf);
1922
1923 free:
1924 free_string(arg_name);
1925 } END_FOR_EACH_PTR(link);
1926 } END_FOR_EACH_PTR(arg);
1927 }
1928
1929 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *link_sm)
1930 {
1931 struct sm_state *compare_sm;
1932 struct string_list *links;
1933 char *link;
1934 struct compare_data *data;
1935 struct var_sym *left, *right;
1936 static char info_buf[256];
1937 const char *right_name;
1938
1939 if (strstr(printed_name, " orig"))
1940 return;
1941
1942 links = link_sm->state->data;
1943 FOR_EACH_PTR(links, link) {
1944 compare_sm = get_sm_state(compare_id, link, NULL);
1945 if (!compare_sm)
1946 continue;
1947 data = compare_sm->state->data;
1948 if (!data || !data->comparison)
1949 continue;
1950
1951 if (ptr_list_size((struct ptr_list *)data->left_vsl) != 1 ||
1952 ptr_list_size((struct ptr_list *)data->right_vsl) != 1)
1953 continue;
1954 left = first_ptr_list((struct ptr_list *)data->left_vsl);
1955 right = first_ptr_list((struct ptr_list *)data->right_vsl);
1956 if (left->sym == right->sym &&
1957 strcmp(left->var, right->var) == 0)
1958 continue;
1959 /*
1960 * Both parameters link to this comparison so only
1961 * record the first one.
1962 */
1963 if (left->sym != link_sm->sym ||
1964 strcmp(left->var, link_sm->name) != 0)
1965 continue;
1966
1967 right_name = get_printed_param_name(call, right->var, right->sym);
1968 if (!right_name)
1969 continue;
1970 snprintf(info_buf, sizeof(info_buf), "%s %s", show_special(data->comparison), right_name);
1971 sql_insert_caller_info(call, PARAM_COMPARE, param, printed_name, info_buf);
1972 } END_FOR_EACH_PTR(link);
1973 }
1974
1975 static void print_return_value_comparison(int return_id, char *return_ranges, struct expression *expr)
1976 {
1977 char *name;
1978 const char *tmp_name;
1979 struct symbol *sym;
1980 int param;
1981 char info_buf[256];
1982
1983 /*
1984 * TODO: This only prints == comparisons. That's probably the most
1985 * useful comparison because == max has lots of implications. But it
1986 * would be good to capture the rest as well.
1987 *
1988 * This information is already in the DB but it's in the parameter math
1989 * bits and it's awkward to use it. This is is the simpler, possibly
1990 * cleaner way, but not necessarily the best, I don't know.
1991 */
1992
1993 if (!expr)
1994 return;
1995 name = expr_to_var_sym(expr, &sym);
1996 if (!name || !sym)
1997 goto free;
1998
1999 param = get_param_num_from_sym(sym);
2000 if (param < 0)
2001 goto free;
2002 if (param_was_set_var_sym(name, sym))
2003 goto free;
2004
2005 tmp_name = get_param_name_var_sym(name, sym);
2006 if (!tmp_name)
2007 goto free;
2008
2009 snprintf(info_buf, sizeof(info_buf), "== $%d%s", param, tmp_name + 1);
2010 sql_insert_return_states(return_id, return_ranges,
2011 PARAM_COMPARE, -1, "$", info_buf);
2012 free:
2013 free_string(name);
2014 }
2015
2016 static void print_return_comparison(int return_id, char *return_ranges, struct expression *expr)
2017 {
2018 struct sm_state *tmp;
2019 struct string_list *links;
2020 char *link;
2021 struct sm_state *sm;
2022 struct compare_data *data;
2023 struct var_sym *left, *right;
2024 int left_param, right_param;
2025 char left_buf[256];
2026 char right_buf[256];
2027 char info_buf[256];
2028 const char *tmp_name;
2029
2030 print_return_value_comparison(return_id, return_ranges, expr);
2031
2032 FOR_EACH_MY_SM(link_id, __get_cur_stree(), tmp) {
2033 if (get_param_num_from_sym(tmp->sym) < 0)
2034 continue;
2035 links = tmp->state->data;
2036 FOR_EACH_PTR(links, link) {
2037 sm = get_sm_state(compare_id, link, NULL);
2038 if (!sm)
2039 continue;
2040 data = sm->state->data;
2041 if (!data || !data->comparison)
2042 continue;
2043 if (ptr_list_size((struct ptr_list *)data->left_vsl) != 1 ||
2044 ptr_list_size((struct ptr_list *)data->right_vsl) != 1)
2045 continue;
2046 left = first_ptr_list((struct ptr_list *)data->left_vsl);
2047 right = first_ptr_list((struct ptr_list *)data->right_vsl);
2048 if (left->sym == right->sym &&
2049 strcmp(left->var, right->var) == 0)
2050 continue;
2051 /*
2052 * Both parameters link to this comparison so only
2053 * record the first one.
2054 */
2055 if (left->sym != tmp->sym ||
2056 strcmp(left->var, tmp->name) != 0)
2057 continue;
2058
2059 if (strstr(right->var, " orig"))
2060 continue;
2061
2062 left_param = get_param_num_from_sym(left->sym);
2063 right_param = get_param_num_from_sym(right->sym);
2064 if (left_param < 0 || right_param < 0)
2065 continue;
2066
2067 tmp_name = get_param_name_var_sym(left->var, left->sym);
2068 if (!tmp_name)
2069 continue;
2070 snprintf(left_buf, sizeof(left_buf), "%s", tmp_name);
2071
2072 tmp_name = get_param_name_var_sym(right->var, right->sym);
2073 if (!tmp_name || tmp_name[0] != '$')
2074 continue;
2075 snprintf(right_buf, sizeof(right_buf), "$%d%s", right_param, tmp_name + 1);
2076
2077 /*
2078 * FIXME: this should reject $ type variables (as
2079 * opposed to $->foo type). Those should come from
2080 * smatch_param_compare_limit.c.
2081 */
2082
2083 snprintf(info_buf, sizeof(info_buf), "%s %s", show_special(data->comparison), right_buf);
2084 sql_insert_return_states(return_id, return_ranges,
2085 PARAM_COMPARE, left_param, left_buf, info_buf);
2086 } END_FOR_EACH_PTR(link);
2087
2088 } END_FOR_EACH_SM(tmp);
2089 }
2090
2091 static int parse_comparison(char **value, int *op)
2092 {
2093
2094 *op = **value;
2095
2096 switch (*op) {
2097 case '<':
2098 (*value)++;
2099 if (**value == '=') {
2100 (*value)++;
2101 *op = SPECIAL_LTE;
2102 }
2103 break;
2104 case '=':
2105 (*value)++;
2106 (*value)++;
2107 *op = SPECIAL_EQUAL;
2108 break;
2109 case '!':
2110 (*value)++;
2111 (*value)++;
2112 *op = SPECIAL_NOTEQUAL;
2113 break;
2114 case '>':
2115 (*value)++;
2116 if (**value == '=') {
2117 (*value)++;
2118 *op = SPECIAL_GTE;
2119 }
2120 break;
2121 default:
2122 return 0;
2123 }
2124
2125 if (**value != ' ') {
2126 sm_msg("internal error parsing comparison. %s", *value);
2127 return 0;
2128 }
2129
2130 (*value)++;
2131 return 1;
2132 }
2133
2134 static int split_op_param_key(char *value, int *op, int *param, char **key)
2135 {
2136 static char buf[256];
2137 char *p;
2138
2139 if (!parse_comparison(&value, op))
2140 return 0;
2141
2142 snprintf(buf, sizeof(buf), value);
2143
2144 p = buf;
2145 if (*p++ != '$')
2146 return 0;
2147
2148 *param = atoi(p);
2149 if (*param < 0 || *param > 99)
2150 return 0;
2151 p++;
2152 if (*param > 9)
2153 p++;
2154 p--;
2155 *p = '$';
2156 *key = p;
2157
2158 return 1;
2159 }
2160
2161 static void db_return_comparison(struct expression *expr, int left_param, char *key, char *value)
2162 {
2163 struct expression *left_arg, *right_arg;
2164 char *left_name = NULL;
2165 struct symbol *left_sym;
2166 char *right_name = NULL;
2167 struct symbol *right_sym;
2168 int op;
2169 int right_param;
2170 char *right_key;
2171 struct var_sym_list *left_vsl = NULL, *right_vsl = NULL;
2172
2173 if (left_param == -1) {
2174 if (expr->type != EXPR_ASSIGNMENT)
2175 return;
2176 left_arg = strip_expr(expr->left);
2177
2178 while (expr->type == EXPR_ASSIGNMENT)
2179 expr = strip_expr(expr->right);
2180 if (expr->type != EXPR_CALL)
2181 return;
2182 } else {
2183 while (expr->type == EXPR_ASSIGNMENT)
2184 expr = strip_expr(expr->right);
2185 if (expr->type != EXPR_CALL)
2186 return;
2187
2188 left_arg = get_argument_from_call_expr(expr->args, left_param);
2189 if (!left_arg)
2190 return;
2191 }
2192
2193 if (!split_op_param_key(value, &op, &right_param, &right_key))
2194 return;
2195
2196 right_arg = get_argument_from_call_expr(expr->args, right_param);
2197 if (!right_arg)
2198 return;
2199
2200 left_name = get_variable_from_key(left_arg, key, &left_sym);
2201 if (!left_name || !left_sym)
2202 goto free;
2203
2204 right_name = get_variable_from_key(right_arg, right_key, &right_sym);
2205 if (!right_name || !right_sym)
2206 goto free;
2207
2208 add_var_sym(&left_vsl, left_name, left_sym);
2209 add_var_sym(&right_vsl, right_name, right_sym);
2210
2211 add_comparison_var_sym(NULL, left_name, left_vsl, op, NULL, right_name, right_vsl);
2212
2213 free:
2214 free_string(left_name);
2215 free_string(right_name);
2216 }
2217
2218 int param_compare_limit_is_impossible(struct expression *expr, int left_param, char *left_key, char *value)
2219 {
2220 struct smatch_state *state;
2221 char *left_name = NULL;
2222 char *right_name = NULL;
2223 struct symbol *left_sym, *right_sym;
2224 struct expression *left_arg, *right_arg;
2225 int op, state_op;
2226 int right_param;
2227 char *right_key;
2228 int ret = 0;
2229 char buf[256];
2230
2231 while (expr->type == EXPR_ASSIGNMENT)
2232 expr = strip_expr(expr->right);
2233 if (expr->type != EXPR_CALL)
2234 return 0;
2235
2236 if (!split_op_param_key(value, &op, &right_param, &right_key))
2237 return 0;
2238
2239 left_arg = get_argument_from_call_expr(expr->args, left_param);
2240 if (!left_arg)
2241 return 0;
2242
2243 right_arg = get_argument_from_call_expr(expr->args, right_param);
2244 if (!right_arg)
2245 return 0;
2246
2247 left_name = get_variable_from_key(left_arg, left_key, &left_sym);
2248 right_name = get_variable_from_key(right_arg, right_key, &right_sym);
2249 if (!left_name || !right_name)
2250 goto free;
2251
2252 snprintf(buf, sizeof(buf), "%s vs %s", left_name, right_name);
2253 state = get_state(compare_id, buf, NULL);
2254 if (!state)
2255 goto free;
2256 state_op = state_to_comparison(state);
2257 if (!state_op)
2258 goto free;
2259
2260 if (!filter_comparison(remove_unsigned_from_comparison(state_op), op))
2261 ret = 1;
2262 free:
2263 free_string(left_name);
2264 free_string(right_name);
2265 return ret;
2266 }
2267
2268 static void free_data(struct symbol *sym)
2269 {
2270 if (__inline_fn)
2271 return;
2272 clear_compare_data_alloc();
2273 }
2274
2275 void register_comparison(int id)
2276 {
2277 compare_id = id;
2278 add_hook(&save_start_states, AFTER_DEF_HOOK);
2279 add_unmatched_state_hook(compare_id, unmatched_comparison);
2280 add_merge_hook(compare_id, &merge_compare_states);
2281 add_hook(&free_data, AFTER_FUNC_HOOK);
2282 add_hook(&match_call_info, FUNCTION_CALL_HOOK);
2283 add_split_return_callback(&print_return_comparison);
2284
2285 select_return_states_hook(PARAM_COMPARE, &db_return_comparison);
2286 }
2287
2288 void register_comparison_late(int id)
2289 {
2290 add_hook(&match_assign, ASSIGNMENT_HOOK);
2291 }
2292
2293 void register_comparison_links(int id)
2294 {
2295 link_id = id;
2296 add_merge_hook(link_id, &merge_links);
2297 add_modification_hook(link_id, &match_modify);
2298
2299 add_member_info_callback(link_id, struct_member_callback);
2300 }
2301
2302 void register_comparison_inc_dec(int id)
2303 {
2304 inc_dec_id = id;
2305 add_modification_hook_late(inc_dec_id, &iter_modify);
2306 }
2307
2308 void register_comparison_inc_dec_links(int id)
2309 {
2310 inc_dec_link_id = id;
2311 set_up_link_functions(inc_dec_id, inc_dec_link_id);
2312 }
2313
2314 static void filter_by_sm(struct sm_state *sm, int op,
2315 struct state_list **true_stack,
2316 struct state_list **false_stack)
2317 {
2318 struct compare_data *data;
2319 int istrue = 0;
2320 int isfalse = 0;
2321
2322 if (!sm)
2323 return;
2324 data = sm->state->data;
2325 if (!data) {
2326 if (sm->merged) {
2327 filter_by_sm(sm->left, op, true_stack, false_stack);
2328 filter_by_sm(sm->right, op, true_stack, false_stack);
2329 }
2330 return;
2331 }
2332
2333 if (data->comparison &&
2334 data->comparison == filter_comparison(data->comparison, op))
2335 istrue = 1;
2336
2337 if (data->comparison &&
2338 data->comparison == filter_comparison(data->comparison, negate_comparison(op)))
2339 isfalse = 1;
2340
2341 if (istrue)
2342 add_ptr_list(true_stack, sm);
2343 if (isfalse)
2344 add_ptr_list(false_stack, sm);
2345
2346 if (sm->merged) {
2347 filter_by_sm(sm->left, op, true_stack, false_stack);
2348 filter_by_sm(sm->right, op, true_stack, false_stack);
2349 }
2350 }
2351
2352 struct sm_state *comparison_implication_hook(struct expression *expr,
2353 struct state_list **true_stack,
2354 struct state_list **false_stack)
2355 {
2356 struct sm_state *sm;
2357 char *left, *right;
2358 int op;
2359 static char buf[256];
2360
2361 if (expr->type != EXPR_COMPARE)
2362 return NULL;
2363
2364 op = expr->op;
2365
2366 left = expr_to_var(expr->left);
2367 right = expr_to_var(expr->right);
2368 if (!left || !right) {
2369 free_string(left);
2370 free_string(right);
2371 return NULL;
2372 }
2373
2374 if (strcmp(left, right) > 0) {
2375 char *tmp = left;
2376
2377 left = right;
2378 right = tmp;
2379 op = flip_comparison(op);
2380 }
2381
2382 snprintf(buf, sizeof(buf), "%s vs %s", left, right);
2383 sm = get_sm_state(compare_id, buf, NULL);
2384 if (!sm)
2385 return NULL;
2386 if (!sm->merged)
2387 return NULL;
2388
2389 filter_by_sm(sm, op, true_stack, false_stack);
2390 if (!*true_stack && !*false_stack)
2391 return NULL;
2392
2393 return sm;
2394 }
Static analysis for C