?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
db/constraints_required.schema: add missing semi-colon
[smatch.git] / smatch_comparison.c
blobd4a453c461b51f45546327507589ae0d097d2b18
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, *tmp;
1156 struct smatch_state *false_state = NULL;
1157 char *state_name = NULL;
1158 int redo, count;
1159
1160 if (expr->type != EXPR_COMPARE)
1161 return;
1162
1163 handle_comparison(expr->left, expr->op, expr->right, &state_name, &false_state);
1164 if (false_state && state_name)
1165 handle_for_loops(expr, state_name, false_state);
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 redo = 0;
1182 left = strip_parens(expr->left);
1183 right = strip_parens(expr->right);
1184 if (get_last_expr_from_expression_stmt(expr->left)) {
1185 left = get_last_expr_from_expression_stmt(expr->left);
1186 redo = 1;
1187 }
1188 if (get_last_expr_from_expression_stmt(expr->right)) {
1189 right = get_last_expr_from_expression_stmt(expr->right);
1190 redo = 1;
1191 }
1192
1193 if (!redo)
1194 return;
1195
1196 count = 0;
1197 while ((tmp = get_assigned_expr(left))) {
1198 if (count++ > 3)
1199 break;
1200 left = strip_expr(tmp);
1201 }
1202 count = 0;
1203 while ((tmp = get_assigned_expr(right))) {
1204 if (count++ > 3)
1205 break;
1206 right = strip_expr(tmp);
1207 }
1208
1209 handle_comparison(left, expr->op, right, NULL, NULL);
1210 }
1211
1212 static void add_comparison_var_sym(
1213 struct expression *left_expr,
1214 const char *left_name, struct var_sym_list *left_vsl,
1215 int comparison,
1216 struct expression *right_expr,
1217 const char *right_name, struct var_sym_list *right_vsl)
1218 {
1219 struct smatch_state *state;
1220 struct var_sym *vs;
1221 char state_name[256];
1222
1223 if (strcmp(left_name, right_name) > 0) {
1224 struct expression *tmp_expr = left_expr;
1225 const char *tmp_name = left_name;
1226 struct var_sym_list *tmp_vsl = left_vsl;
1227
1228 left_expr = right_expr;
1229 left_name = right_name;
1230 left_vsl = right_vsl;
1231 right_expr = tmp_expr;
1232 right_name = tmp_name;
1233 right_vsl = tmp_vsl;
1234 comparison = flip_comparison(comparison);
1235 }
1236 snprintf(state_name, sizeof(state_name), "%s vs %s", left_name, right_name);
1237 state = alloc_compare_state(
1238 left_expr, left_name, left_vsl,
1239 comparison,
1240 right_expr, right_name, right_vsl);
1241
1242 set_state(compare_id, state_name, NULL, state);
1243
1244 FOR_EACH_PTR(left_vsl, vs) {
1245 save_link_var_sym(vs->var, vs->sym, state_name);
1246 } END_FOR_EACH_PTR(vs);
1247 FOR_EACH_PTR(right_vsl, vs) {
1248 save_link_var_sym(vs->var, vs->sym, state_name);
1249 } END_FOR_EACH_PTR(vs);
1250 }
1251
1252 static void add_comparison(struct expression *left, int comparison, struct expression *right)
1253 {
1254 char *left_name = NULL;
1255 char *right_name = NULL;
1256 struct symbol *left_sym, *right_sym;
1257 struct var_sym_list *left_vsl, *right_vsl;
1258 struct smatch_state *state;
1259 char state_name[256];
1260
1261 left_name = chunk_to_var_sym(left, &left_sym);
1262 if (!left_name)
1263 goto free;
1264 left_vsl = expr_to_vsl(left);
1265 right_name = chunk_to_var_sym(right, &right_sym);
1266 if (!right_name)
1267 goto free;
1268 right_vsl = expr_to_vsl(right);
1269
1270 if (strcmp(left_name, right_name) > 0) {
1271 struct expression *tmp_expr = left;
1272 struct symbol *tmp_sym = left_sym;
1273 char *tmp_name = left_name;
1274 struct var_sym_list *tmp_vsl = left_vsl;
1275
1276 left = right;
1277 left_name = right_name;
1278 left_sym = right_sym;
1279 left_vsl = right_vsl;
1280 right = tmp_expr;
1281 right_name = tmp_name;
1282 right_sym = tmp_sym;
1283 right_vsl = tmp_vsl;
1284 comparison = flip_comparison(comparison);
1285 }
1286 snprintf(state_name, sizeof(state_name), "%s vs %s", left_name, right_name);
1287 state = alloc_compare_state(
1288 left, left_name, left_vsl,
1289 comparison,
1290 right, right_name, right_vsl);
1291
1292 set_state(compare_id, state_name, NULL, state);
1293 save_link(left, state_name);
1294 save_link(right, state_name);
1295
1296 free:
1297 free_string(left_name);
1298 free_string(right_name);
1299 }
1300
1301 static void match_assign_add(struct expression *expr)
1302 {
1303 struct expression *right;
1304 struct expression *r_left, *r_right;
1305 sval_t left_tmp, right_tmp;
1306
1307 right = strip_expr(expr->right);
1308 r_left = strip_expr(right->left);
1309 r_right = strip_expr(right->right);
1310
1311 get_absolute_min(r_left, &left_tmp);
1312 get_absolute_min(r_right, &right_tmp);
1313
1314 if (left_tmp.value > 0)
1315 add_comparison(expr->left, '>', r_right);
1316 else if (left_tmp.value == 0)
1317 add_comparison(expr->left, SPECIAL_GTE, r_right);
1318
1319 if (right_tmp.value > 0)
1320 add_comparison(expr->left, '>', r_left);
1321 else if (right_tmp.value == 0)
1322 add_comparison(expr->left, SPECIAL_GTE, r_left);
1323 }
1324
1325 static void match_assign_sub(struct expression *expr)
1326 {
1327 struct expression *right;
1328 struct expression *r_left, *r_right;
1329 int comparison;
1330 sval_t min;
1331
1332 right = strip_expr(expr->right);
1333 r_left = strip_expr(right->left);
1334 r_right = strip_expr(right->right);
1335
1336 if (get_absolute_min(r_right, &min) && sval_is_negative(min))
1337 return;
1338
1339 comparison = get_comparison(r_left, r_right);
1340
1341 switch (comparison) {
1342 case '>':
1343 case SPECIAL_GTE:
1344 if (implied_not_equal(r_right, 0))
1345 add_comparison(expr->left, '>', r_left);
1346 else
1347 add_comparison(expr->left, SPECIAL_GTE, r_left);
1348 return;
1349 }
1350 }
1351
1352 static void match_assign_divide(struct expression *expr)
1353 {
1354 struct expression *right;
1355 struct expression *r_left, *r_right;
1356 sval_t min;
1357
1358 right = strip_expr(expr->right);
1359 r_left = strip_expr(right->left);
1360 r_right = strip_expr(right->right);
1361 if (!get_implied_min(r_right, &min) || min.value <= 1)
1362 return;
1363
1364 add_comparison(expr->left, '<', r_left);
1365 }
1366
1367 static void match_binop_assign(struct expression *expr)
1368 {
1369 struct expression *right;
1370
1371 right = strip_expr(expr->right);
1372 if (right->op == '+')
1373 match_assign_add(expr);
1374 if (right->op == '-')
1375 match_assign_sub(expr);
1376 if (right->op == '/')
1377 match_assign_divide(expr);
1378 }
1379
1380 static void copy_comparisons(struct expression *left, struct expression *right)
1381 {
1382 struct string_list *links;
1383 struct smatch_state *state;
1384 struct compare_data *data;
1385 struct symbol *left_sym, *right_sym;
1386 char *left_var = NULL;
1387 char *right_var = NULL;
1388 struct var_sym_list *left_vsl;
1389 struct expression *expr;
1390 const char *var;
1391 struct var_sym_list *vsl;
1392 int comparison;
1393 char *tmp;
1394
1395 left_var = chunk_to_var_sym(left, &left_sym);
1396 if (!left_var)
1397 goto done;
1398 left_vsl = expr_to_vsl(left);
1399 right_var = chunk_to_var_sym(right, &right_sym);
1400 if (!right_var)
1401 goto done;
1402
1403 state = get_state(link_id, right_var, right_sym);
1404 if (!state)
1405 return;
1406 links = state->data;
1407
1408 FOR_EACH_PTR(links, tmp) {
1409 state = get_state(compare_id, tmp, NULL);
1410 if (!state || !state->data)
1411 continue;
1412 data = state->data;
1413 comparison = data->comparison;
1414 expr = data->right;
1415 var = data->right_var;
1416 vsl = data->right_vsl;
1417 if (strcmp(var, right_var) == 0) {
1418 expr = data->left;
1419 var = data->left_var;
1420 vsl = data->left_vsl;
1421 comparison = flip_comparison(comparison);
1422 }
1423 add_comparison_var_sym(left, left_var, left_vsl, comparison, expr, var, vsl);
1424 } END_FOR_EACH_PTR(tmp);
1425
1426 done:
1427 free_string(right_var);
1428 }
1429
1430 static void match_assign(struct expression *expr)
1431 {
1432 struct expression *right;
1433
1434 if (expr->op != '=')
1435 return;
1436 if (__in_fake_assign || outside_of_function())
1437 return;
1438
1439 if (is_struct(expr->left))
1440 return;
1441
1442 copy_comparisons(expr->left, expr->right);
1443 add_comparison(expr->left, SPECIAL_EQUAL, expr->right);
1444
1445 right = strip_expr(expr->right);
1446 if (right->type == EXPR_BINOP)
1447 match_binop_assign(expr);
1448 }
1449
1450 int get_comparison_strings(const char *one, const char *two)
1451 {
1452 char buf[256];
1453 struct smatch_state *state;
1454 int invert = 0;
1455 int ret = 0;
1456
1457 if (!one || !two)
1458 return 0;
1459
1460 if (strcmp(one, two) == 0)
1461 return SPECIAL_EQUAL;
1462
1463 if (strcmp(one, two) > 0) {
1464 const char *tmp = one;
1465
1466 one = two;
1467 two = tmp;
1468 invert = 1;
1469 }
1470
1471 snprintf(buf, sizeof(buf), "%s vs %s", one, two);
1472 state = get_state(compare_id, buf, NULL);
1473 if (state)
1474 ret = state_to_comparison(state);
1475
1476 if (invert)
1477 ret = flip_comparison(ret);
1478
1479 return ret;
1480 }
1481
1482 int get_comparison(struct expression *a, struct expression *b)
1483 {
1484 char *one = NULL;
1485 char *two = NULL;
1486 int ret = 0;
1487
1488 a = strip_parens(a);
1489 b = strip_parens(b);
1490
1491 move_plus_to_minus(&a, &b);
1492
1493 one = chunk_to_var(a);
1494 if (!one)
1495 goto free;
1496 two = chunk_to_var(b);
1497 if (!two)
1498 goto free;
1499
1500 ret = get_comparison_strings(one, two);
1501 if (ret)
1502 goto free;
1503
1504 if (is_plus_one(a) || is_minus_one(a)) {
1505 free_string(one);
1506 one = chunk_to_var(a->left);
1507 ret = get_comparison_strings(one, two);
1508 } else if (is_plus_one(b) || is_minus_one(b)) {
1509 free_string(two);
1510 two = chunk_to_var(b->left);
1511 ret = get_comparison_strings(one, two);
1512 }
1513
1514 if (!ret)
1515 goto free;
1516
1517 if ((is_plus_one(a) || is_minus_one(b)) && ret == '<')
1518 ret = SPECIAL_LTE;
1519 else if ((is_minus_one(a) || is_plus_one(b)) && ret == '>')
1520 ret = SPECIAL_GTE;
1521 else
1522 ret = 0;
1523
1524 free:
1525 free_string(one);
1526 free_string(two);
1527 return ret;
1528 }
1529
1530 int possible_comparison(struct expression *a, int comparison, struct expression *b)
1531 {
1532 char *one = NULL;
1533 char *two = NULL;
1534 int ret = 0;
1535 char buf[256];
1536 struct sm_state *sm;
1537 int saved;
1538
1539 one = chunk_to_var(a);
1540 if (!one)
1541 goto free;
1542 two = chunk_to_var(b);
1543 if (!two)
1544 goto free;
1545
1546
1547 if (strcmp(one, two) == 0 && comparison == SPECIAL_EQUAL) {
1548 ret = 1;
1549 goto free;
1550 }
1551
1552 if (strcmp(one, two) > 0) {
1553 char *tmp = one;
1554
1555 one = two;
1556 two = tmp;
1557 comparison = flip_comparison(comparison);
1558 }
1559
1560 snprintf(buf, sizeof(buf), "%s vs %s", one, two);
1561 sm = get_sm_state(compare_id, buf, NULL);
1562 if (!sm)
1563 goto free;
1564
1565 FOR_EACH_PTR(sm->possible, sm) {
1566 if (!sm->state->data)
1567 continue;
1568 saved = ((struct compare_data *)sm->state->data)->comparison;
1569 if (saved == comparison)
1570 ret = 1;
1571 if (comparison == SPECIAL_EQUAL &&
1572 (saved == SPECIAL_LTE ||
1573 saved == SPECIAL_GTE ||
1574 saved == SPECIAL_UNSIGNED_LTE ||
1575 saved == SPECIAL_UNSIGNED_GTE))
1576 ret = 1;
1577 if (ret == 1)
1578 goto free;
1579 } END_FOR_EACH_PTR(sm);
1580
1581 return ret;
1582 free:
1583 free_string(one);
1584 free_string(two);
1585 return ret;
1586 }
1587
1588 struct state_list *get_all_comparisons(struct expression *expr)
1589 {
1590 struct smatch_state *state;
1591 struct string_list *links;
1592 struct state_list *ret = NULL;
1593 struct sm_state *sm;
1594 char *tmp;
1595
1596 state = get_state_chunk(link_id, expr);
1597 if (!state)
1598 return NULL;
1599 links = state->data;
1600
1601 FOR_EACH_PTR(links, tmp) {
1602 sm = get_sm_state(compare_id, tmp, NULL);
1603 if (!sm)
1604 continue;
1605 // FIXME have to compare name with vsl
1606 add_ptr_list(&ret, sm);
1607 } END_FOR_EACH_PTR(tmp);
1608
1609 return ret;
1610 }
1611
1612 struct state_list *get_all_possible_equal_comparisons(struct expression *expr)
1613 {
1614 struct smatch_state *state;
1615 struct string_list *links;
1616 struct state_list *ret = NULL;
1617 struct sm_state *sm;
1618 char *tmp;
1619
1620 state = get_state_chunk(link_id, expr);
1621 if (!state)
1622 return NULL;
1623 links = state->data;
1624
1625 FOR_EACH_PTR(links, tmp) {
1626 sm = get_sm_state(compare_id, tmp, NULL);
1627 if (!sm)
1628 continue;
1629 if (!strchr(sm->state->name, '='))
1630 continue;
1631 if (strcmp(sm->state->name, "!=") == 0)
1632 continue;
1633 add_ptr_list(&ret, sm);
1634 } END_FOR_EACH_PTR(tmp);
1635
1636 return ret;
1637 }
1638
1639 struct state_list *get_all_possible_not_equal_comparisons(struct expression *expr)
1640 {
1641 struct smatch_state *state;
1642 struct string_list *links;
1643 struct state_list *ret = NULL;
1644 struct sm_state *sm;
1645 struct sm_state *possible;
1646 char *link;
1647
1648 return NULL;
1649
1650 state = get_state_chunk(link_id, expr);
1651 if (!state)
1652 return NULL;
1653 links = state->data;
1654
1655 FOR_EACH_PTR(links, link) {
1656 sm = get_sm_state(compare_id, link, NULL);
1657 if (!sm)
1658 continue;
1659 FOR_EACH_PTR(sm->possible, possible) {
1660 if (strcmp(possible->state->name, "!=") != 0)
1661 continue;
1662 add_ptr_list(&ret, sm);
1663 break;
1664 } END_FOR_EACH_PTR(link);
1665 } END_FOR_EACH_PTR(link);
1666
1667 return ret;
1668 }
1669
1670 static void update_links_from_call(struct expression *left,
1671 int left_compare,
1672 struct expression *right)
1673 {
1674 struct string_list *links;
1675 struct smatch_state *state;
1676 struct compare_data *data;
1677 struct symbol *left_sym, *right_sym;
1678 char *left_var = NULL;
1679 char *right_var = NULL;
1680 struct var_sym_list *left_vsl;
1681 struct expression *expr;
1682 const char *var;
1683 struct var_sym_list *vsl;
1684 int comparison;
1685 char *tmp;
1686
1687 left_var = chunk_to_var_sym(left, &left_sym);
1688 if (!left_var)
1689 goto done;
1690 left_vsl = expr_to_vsl(left);
1691 right_var = chunk_to_var_sym(right, &right_sym);
1692 if (!right_var)
1693 goto done;
1694
1695 state = get_state(link_id, right_var, right_sym);
1696 if (!state)
1697 return;
1698 links = state->data;
1699
1700 FOR_EACH_PTR(links, tmp) {
1701 state = get_state(compare_id, tmp, NULL);
1702 if (!state || !state->data)
1703 continue;
1704 data = state->data;
1705 comparison = data->comparison;
1706 expr = data->right;
1707 var = data->right_var;
1708 vsl = data->right_vsl;
1709 if (strcmp(var, right_var) == 0) {
1710 expr = data->left;
1711 var = data->left_var;
1712 vsl = data->left_vsl;
1713 comparison = flip_comparison(comparison);
1714 }
1715 comparison = combine_comparisons(left_compare, comparison);
1716 if (!comparison)
1717 continue;
1718 add_comparison_var_sym(left, left_var, left_vsl, comparison, expr, var, vsl);
1719 } END_FOR_EACH_PTR(tmp);
1720
1721 done:
1722 free_string(right_var);
1723 }
1724
1725 void __add_return_comparison(struct expression *call, const char *range)
1726 {
1727 struct expression *arg;
1728 int comparison;
1729 char buf[4];
1730
1731 if (!str_to_comparison_arg(range, call, &comparison, &arg))
1732 return;
1733 snprintf(buf, sizeof(buf), "%s", show_special(comparison));
1734 update_links_from_call(call, comparison, arg);
1735 add_comparison(call, comparison, arg);
1736 }
1737
1738 void __add_comparison_info(struct expression *expr, struct expression *call, const char *range)
1739 {
1740 copy_comparisons(expr, call);
1741 }
1742
1743 static char *get_mask_comparison(struct expression *expr, int ignore)
1744 {
1745 struct expression *tmp, *right;
1746 int count, param;
1747 char buf[256];
1748
1749 /* The return value for "return foo & param;" is <= param */
1750
1751 count = 0;
1752 while ((tmp = get_assigned_expr(expr))) {
1753 expr = strip_expr(tmp);
1754 if (count++ > 4)
1755 break;
1756 }
1757
1758 if (expr->type != EXPR_BINOP || expr->op != '&')
1759 return NULL;
1760
1761 right = strip_expr(expr->right);
1762 param = get_param_num(right);
1763
1764 if (param == ignore)
1765 return NULL;
1766
1767 snprintf(buf, sizeof(buf), "[<=$%d]", param);
1768 return alloc_sname(buf);
1769 }
1770
1771 static char *range_comparison_to_param_helper(struct expression *expr, char starts_with, int ignore)
1772 {
1773 struct symbol *param;
1774 char *var = NULL;
1775 char buf[256];
1776 char *ret_str = NULL;
1777 int compare;
1778 int i;
1779
1780 if (!expr)
1781 return NULL;
1782
1783 var = chunk_to_var(expr);
1784 if (!var)
1785 goto try_mask;
1786
1787 i = -1;
1788 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
1789 i++;
1790 if (i == ignore)
1791 continue;
1792 if (!param->ident)
1793 continue;
1794 snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
1795 compare = get_comparison_strings(var, buf);
1796 if (!compare)
1797 continue;
1798 if (show_special(compare)[0] != starts_with)
1799 continue;
1800 snprintf(buf, sizeof(buf), "[%s$%d]", show_special(compare), i);
1801 ret_str = alloc_sname(buf);
1802 break;
1803 } END_FOR_EACH_PTR(param);
1804
1805 free_string(var);
1806 if (!ret_str)
1807 goto try_mask;
1808
1809 return ret_str;
1810
1811 try_mask:
1812 if (starts_with == '<')
1813 ret_str = get_mask_comparison(expr, ignore);
1814 return ret_str;
1815 }
1816
1817 char *name_sym_to_param_comparison(const char *name, struct symbol *sym)
1818 {
1819 struct symbol *param;
1820 char buf[256];
1821 int compare;
1822 int i;
1823
1824 i = -1;
1825 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
1826 i++;
1827 if (!param->ident)
1828 continue;
1829 snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
1830 compare = get_comparison_strings(name, buf);
1831 if (!compare)
1832 continue;
1833 snprintf(buf, sizeof(buf), "[%s$%d]", show_special(compare), i);
1834 return alloc_sname(buf);
1835 } END_FOR_EACH_PTR(param);
1836
1837 return NULL;
1838 }
1839
1840 char *expr_equal_to_param(struct expression *expr, int ignore)
1841 {
1842 return range_comparison_to_param_helper(expr, '=', ignore);
1843 }
1844
1845 char *expr_lte_to_param(struct expression *expr, int ignore)
1846 {
1847 return range_comparison_to_param_helper(expr, '<', ignore);
1848 }
1849
1850 char *expr_param_comparison(struct expression *expr, int ignore)
1851 {
1852 struct symbol *param;
1853 char *var = NULL;
1854 char buf[256];
1855 char *ret_str = NULL;
1856 int compare;
1857 int i;
1858
1859 var = chunk_to_var(expr);
1860 if (!var)
1861 goto free;
1862
1863 i = -1;
1864 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
1865 i++;
1866 if (i == ignore)
1867 continue;
1868 if (!param->ident)
1869 continue;
1870 snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
1871 compare = get_comparison_strings(var, buf);
1872 if (!compare)
1873 continue;
1874 snprintf(buf, sizeof(buf), "[%s$%d]", show_special(compare), i);
1875 ret_str = alloc_sname(buf);
1876 break;
1877 } END_FOR_EACH_PTR(param);
1878
1879 free:
1880 free_string(var);
1881 return ret_str;
1882 }
1883
1884 char *get_printed_param_name(struct expression *call, const char *param_name, struct symbol *param_sym)
1885 {
1886 struct expression *arg;
1887 char *name;
1888 struct symbol *sym;
1889 static char buf[256];
1890 int len;
1891 int i;
1892
1893 i = -1;
1894 FOR_EACH_PTR(call->args, arg) {
1895 i++;
1896
1897 name = expr_to_var_sym(arg, &sym);
1898 if (!name || !sym)
1899 continue;
1900 if (sym != param_sym)
1901 continue;
1902
1903 len = strlen(name);
1904 if (strncmp(name, param_name, len) != 0)
1905 continue;
1906 if (param_name[len] == '\0') {
1907 snprintf(buf, sizeof(buf), "$%d", i);
1908 return buf;
1909 }
1910 if (param_name[len] != '-')
1911 continue;
1912 snprintf(buf, sizeof(buf), "$%d%s", i, param_name + len);
1913 return buf;
1914 } END_FOR_EACH_PTR(arg);
1915
1916 return NULL;
1917 }
1918
1919 static void match_call_info(struct expression *expr)
1920 {
1921 struct expression *arg;
1922 struct smatch_state *state;
1923 struct sm_state *sm;
1924 struct compare_data *data;
1925 int comparison;
1926 struct string_list *links;
1927 char *arg_name;
1928 const char *right_name;
1929 char *link;
1930 char info_buf[256];
1931 int i;
1932
1933 i = -1;
1934 FOR_EACH_PTR(expr->args, arg) {
1935 i++;
1936
1937 state = get_state_chunk(link_id, arg);
1938 if (!state)
1939 continue;
1940
1941 links = state->data;
1942 FOR_EACH_PTR(links, link) {
1943 struct var_sym_list *right_vsl;
1944 struct var_sym *right_vs;
1945
1946
1947 if (strstr(link, " orig"))
1948 continue;
1949 sm = get_sm_state(compare_id, link, NULL);
1950 if (!sm)
1951 continue;
1952 data = sm->state->data;
1953 if (!data || !data->comparison)
1954 continue;
1955 arg_name = expr_to_var(arg);
1956 if (!arg_name)
1957 continue;
1958
1959 right_vsl = NULL;
1960 if (strcmp(data->left_var, arg_name) == 0) {
1961 comparison = data->comparison;
1962 right_name = data->right_var;
1963 right_vsl = data->right_vsl;
1964 } else if (strcmp(data->right_var, arg_name) == 0) {
1965 comparison = flip_comparison(data->comparison);
1966 right_name = data->left_var;
1967 right_vsl = data->left_vsl;
1968 }
1969 if (!right_vsl || ptr_list_size((struct ptr_list *)right_vsl) != 1)
1970 goto free;
1971
1972 right_vs = first_ptr_list((struct ptr_list *)right_vsl);
1973 if (strcmp(right_vs->var, right_name) != 0)
1974 goto free;
1975 right_name = get_printed_param_name(expr, right_vs->var, right_vs->sym);
1976 if (!right_name)
1977 goto free;
1978 snprintf(info_buf, sizeof(info_buf), "%s %s", show_special(comparison), right_name);
1979 sql_insert_caller_info(expr, PARAM_COMPARE, i, "$", info_buf);
1980
1981 free:
1982 free_string(arg_name);
1983 } END_FOR_EACH_PTR(link);
1984 } END_FOR_EACH_PTR(arg);
1985 }
1986
1987 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *link_sm)
1988 {
1989 struct sm_state *compare_sm;
1990 struct string_list *links;
1991 char *link;
1992 struct compare_data *data;
1993 struct var_sym *left, *right;
1994 static char info_buf[256];
1995 const char *right_name;
1996
1997 if (strstr(printed_name, " orig"))
1998 return;
1999
2000 links = link_sm->state->data;
2001 FOR_EACH_PTR(links, link) {
2002 compare_sm = get_sm_state(compare_id, link, NULL);
2003 if (!compare_sm)
2004 continue;
2005 data = compare_sm->state->data;
2006 if (!data || !data->comparison)
2007 continue;
2008
2009 if (ptr_list_size((struct ptr_list *)data->left_vsl) != 1 ||
2010 ptr_list_size((struct ptr_list *)data->right_vsl) != 1)
2011 continue;
2012 left = first_ptr_list((struct ptr_list *)data->left_vsl);
2013 right = first_ptr_list((struct ptr_list *)data->right_vsl);
2014 if (left->sym == right->sym &&
2015 strcmp(left->var, right->var) == 0)
2016 continue;
2017 /*
2018 * Both parameters link to this comparison so only
2019 * record the first one.
2020 */
2021 if (left->sym != link_sm->sym ||
2022 strcmp(left->var, link_sm->name) != 0)
2023 continue;
2024
2025 right_name = get_printed_param_name(call, right->var, right->sym);
2026 if (!right_name)
2027 continue;
2028 snprintf(info_buf, sizeof(info_buf), "%s %s", show_special(data->comparison), right_name);
2029 sql_insert_caller_info(call, PARAM_COMPARE, param, printed_name, info_buf);
2030 } END_FOR_EACH_PTR(link);
2031 }
2032
2033 static void print_return_value_comparison(int return_id, char *return_ranges, struct expression *expr)
2034 {
2035 char *name;
2036 const char *tmp_name;
2037 struct symbol *sym;
2038 int param;
2039 char info_buf[256];
2040
2041 /*
2042 * TODO: This only prints == comparisons. That's probably the most
2043 * useful comparison because == max has lots of implications. But it
2044 * would be good to capture the rest as well.
2045 *
2046 * This information is already in the DB but it's in the parameter math
2047 * bits and it's awkward to use it. This is is the simpler, possibly
2048 * cleaner way, but not necessarily the best, I don't know.
2049 */
2050
2051 if (!expr)
2052 return;
2053 name = expr_to_var_sym(expr, &sym);
2054 if (!name || !sym)
2055 goto free;
2056
2057 param = get_param_num_from_sym(sym);
2058 if (param < 0)
2059 goto free;
2060 if (param_was_set_var_sym(name, sym))
2061 goto free;
2062
2063 tmp_name = get_param_name_var_sym(name, sym);
2064 if (!tmp_name)
2065 goto free;
2066
2067 snprintf(info_buf, sizeof(info_buf), "== $%d%s", param, tmp_name + 1);
2068 sql_insert_return_states(return_id, return_ranges,
2069 PARAM_COMPARE, -1, "$", info_buf);
2070 free:
2071 free_string(name);
2072 }
2073
2074 static void print_return_comparison(int return_id, char *return_ranges, struct expression *expr)
2075 {
2076 struct sm_state *tmp;
2077 struct string_list *links;
2078 char *link;
2079 struct sm_state *sm;
2080 struct compare_data *data;
2081 struct var_sym *left, *right;
2082 int left_param, right_param;
2083 char left_buf[256];
2084 char right_buf[256];
2085 char info_buf[256];
2086 const char *tmp_name;
2087
2088 print_return_value_comparison(return_id, return_ranges, expr);
2089
2090 FOR_EACH_MY_SM(link_id, __get_cur_stree(), tmp) {
2091 if (get_param_num_from_sym(tmp->sym) < 0)
2092 continue;
2093 links = tmp->state->data;
2094 FOR_EACH_PTR(links, link) {
2095 sm = get_sm_state(compare_id, link, NULL);
2096 if (!sm)
2097 continue;
2098 data = sm->state->data;
2099 if (!data || !data->comparison)
2100 continue;
2101 if (ptr_list_size((struct ptr_list *)data->left_vsl) != 1 ||
2102 ptr_list_size((struct ptr_list *)data->right_vsl) != 1)
2103 continue;
2104 left = first_ptr_list((struct ptr_list *)data->left_vsl);
2105 right = first_ptr_list((struct ptr_list *)data->right_vsl);
2106 if (left->sym == right->sym &&
2107 strcmp(left->var, right->var) == 0)
2108 continue;
2109 /*
2110 * Both parameters link to this comparison so only
2111 * record the first one.
2112 */
2113 if (left->sym != tmp->sym ||
2114 strcmp(left->var, tmp->name) != 0)
2115 continue;
2116
2117 if (strstr(right->var, " orig"))
2118 continue;
2119
2120 left_param = get_param_num_from_sym(left->sym);
2121 right_param = get_param_num_from_sym(right->sym);
2122 if (left_param < 0 || right_param < 0)
2123 continue;
2124
2125 tmp_name = get_param_name_var_sym(left->var, left->sym);
2126 if (!tmp_name)
2127 continue;
2128 snprintf(left_buf, sizeof(left_buf), "%s", tmp_name);
2129
2130 tmp_name = get_param_name_var_sym(right->var, right->sym);
2131 if (!tmp_name || tmp_name[0] != '$')
2132 continue;
2133 snprintf(right_buf, sizeof(right_buf), "$%d%s", right_param, tmp_name + 1);
2134
2135 /*
2136 * FIXME: this should reject $ type variables (as
2137 * opposed to $->foo type). Those should come from
2138 * smatch_param_compare_limit.c.
2139 */
2140
2141 snprintf(info_buf, sizeof(info_buf), "%s %s", show_special(data->comparison), right_buf);
2142 sql_insert_return_states(return_id, return_ranges,
2143 PARAM_COMPARE, left_param, left_buf, info_buf);
2144 } END_FOR_EACH_PTR(link);
2145
2146 } END_FOR_EACH_SM(tmp);
2147 }
2148
2149 static int parse_comparison(char **value, int *op)
2150 {
2151
2152 *op = **value;
2153
2154 switch (*op) {
2155 case '<':
2156 (*value)++;
2157 if (**value == '=') {
2158 (*value)++;
2159 *op = SPECIAL_LTE;
2160 }
2161 break;
2162 case '=':
2163 (*value)++;
2164 (*value)++;
2165 *op = SPECIAL_EQUAL;
2166 break;
2167 case '!':
2168 (*value)++;
2169 (*value)++;
2170 *op = SPECIAL_NOTEQUAL;
2171 break;
2172 case '>':
2173 (*value)++;
2174 if (**value == '=') {
2175 (*value)++;
2176 *op = SPECIAL_GTE;
2177 }
2178 break;
2179 default:
2180 return 0;
2181 }
2182
2183 if (**value != ' ') {
2184 sm_msg("internal error parsing comparison. %s", *value);
2185 return 0;
2186 }
2187
2188 (*value)++;
2189 return 1;
2190 }
2191
2192 static int split_op_param_key(char *value, int *op, int *param, char **key)
2193 {
2194 static char buf[256];
2195 char *p;
2196
2197 if (!parse_comparison(&value, op))
2198 return 0;
2199
2200 snprintf(buf, sizeof(buf), value);
2201
2202 p = buf;
2203 if (*p++ != '$')
2204 return 0;
2205
2206 *param = atoi(p);
2207 if (*param < 0 || *param > 99)
2208 return 0;
2209 p++;
2210 if (*param > 9)
2211 p++;
2212 p--;
2213 *p = '$';
2214 *key = p;
2215
2216 return 1;
2217 }
2218
2219 static void db_return_comparison(struct expression *expr, int left_param, char *key, char *value)
2220 {
2221 struct expression *left_arg, *right_arg;
2222 char *left_name = NULL;
2223 struct symbol *left_sym;
2224 char *right_name = NULL;
2225 struct symbol *right_sym;
2226 int op;
2227 int right_param;
2228 char *right_key;
2229 struct var_sym_list *left_vsl = NULL, *right_vsl = NULL;
2230
2231 if (left_param == -1) {
2232 if (expr->type != EXPR_ASSIGNMENT)
2233 return;
2234 left_arg = strip_expr(expr->left);
2235
2236 while (expr->type == EXPR_ASSIGNMENT)
2237 expr = strip_expr(expr->right);
2238 if (expr->type != EXPR_CALL)
2239 return;
2240 } else {
2241 while (expr->type == EXPR_ASSIGNMENT)
2242 expr = strip_expr(expr->right);
2243 if (expr->type != EXPR_CALL)
2244 return;
2245
2246 left_arg = get_argument_from_call_expr(expr->args, left_param);
2247 if (!left_arg)
2248 return;
2249 }
2250
2251 if (!split_op_param_key(value, &op, &right_param, &right_key))
2252 return;
2253
2254 right_arg = get_argument_from_call_expr(expr->args, right_param);
2255 if (!right_arg)
2256 return;
2257
2258 left_name = get_variable_from_key(left_arg, key, &left_sym);
2259 if (!left_name || !left_sym)
2260 goto free;
2261
2262 right_name = get_variable_from_key(right_arg, right_key, &right_sym);
2263 if (!right_name || !right_sym)
2264 goto free;
2265
2266 add_var_sym(&left_vsl, left_name, left_sym);
2267 add_var_sym(&right_vsl, right_name, right_sym);
2268
2269 add_comparison_var_sym(NULL, left_name, left_vsl, op, NULL, right_name, right_vsl);
2270
2271 free:
2272 free_string(left_name);
2273 free_string(right_name);
2274 }
2275
2276 int param_compare_limit_is_impossible(struct expression *expr, int left_param, char *left_key, char *value)
2277 {
2278 struct smatch_state *state;
2279 char *left_name = NULL;
2280 char *right_name = NULL;
2281 struct symbol *left_sym, *right_sym;
2282 struct expression *left_arg, *right_arg;
2283 int op, state_op;
2284 int right_param;
2285 char *right_key;
2286 int ret = 0;
2287 char buf[256];
2288
2289 while (expr->type == EXPR_ASSIGNMENT)
2290 expr = strip_expr(expr->right);
2291 if (expr->type != EXPR_CALL)
2292 return 0;
2293
2294 if (!split_op_param_key(value, &op, &right_param, &right_key))
2295 return 0;
2296
2297 left_arg = get_argument_from_call_expr(expr->args, left_param);
2298 if (!left_arg)
2299 return 0;
2300
2301 right_arg = get_argument_from_call_expr(expr->args, right_param);
2302 if (!right_arg)
2303 return 0;
2304
2305 left_name = get_variable_from_key(left_arg, left_key, &left_sym);
2306 right_name = get_variable_from_key(right_arg, right_key, &right_sym);
2307 if (!left_name || !right_name)
2308 goto free;
2309
2310 snprintf(buf, sizeof(buf), "%s vs %s", left_name, right_name);
2311 state = get_state(compare_id, buf, NULL);
2312 if (!state)
2313 goto free;
2314 state_op = state_to_comparison(state);
2315 if (!state_op)
2316 goto free;
2317
2318 if (!filter_comparison(remove_unsigned_from_comparison(state_op), op))
2319 ret = 1;
2320 free:
2321 free_string(left_name);
2322 free_string(right_name);
2323 return ret;
2324 }
2325
2326 int impossibly_high_comparison(struct expression *expr)
2327 {
2328 struct smatch_state *link_state;
2329 struct sm_state *sm;
2330 struct string_list *links;
2331 char *link;
2332 struct compare_data *data;
2333
2334 link_state = get_state_expr(link_id, expr);
2335 if (!link_state) {
2336 if (expr->type == EXPR_BINOP &&
2337 (impossibly_high_comparison(expr->left) ||
2338 impossibly_high_comparison(expr->right)))
2339 return 1;
2340 return 0;
2341 }
2342
2343 links = link_state->data;
2344 FOR_EACH_PTR(links, link) {
2345 sm = get_sm_state(compare_id, link, NULL);
2346 if (!sm)
2347 continue;
2348 data = sm->state->data;
2349 if (!data)
2350 continue;
2351 if (!possibly_true(data->left, data->comparison, data->right))
2352 return 1;
2353 } END_FOR_EACH_PTR(link);
2354
2355 return 0;
2356 }
2357
2358 static void free_data(struct symbol *sym)
2359 {
2360 if (__inline_fn)
2361 return;
2362 clear_compare_data_alloc();
2363 }
2364
2365 void register_comparison(int id)
2366 {
2367 compare_id = id;
2368 add_hook(&save_start_states, AFTER_DEF_HOOK);
2369 add_unmatched_state_hook(compare_id, unmatched_comparison);
2370 add_merge_hook(compare_id, &merge_compare_states);
2371 add_hook(&free_data, AFTER_FUNC_HOOK);
2372 add_hook(&match_call_info, FUNCTION_CALL_HOOK);
2373 add_split_return_callback(&print_return_comparison);
2374
2375 select_return_states_hook(PARAM_COMPARE, &db_return_comparison);
2376 }
2377
2378 void register_comparison_late(int id)
2379 {
2380 add_hook(&match_assign, ASSIGNMENT_HOOK);
2381 }
2382
2383 void register_comparison_links(int id)
2384 {
2385 link_id = id;
2386 add_merge_hook(link_id, &merge_links);
2387 add_modification_hook(link_id, &match_modify);
2388
2389 add_member_info_callback(link_id, struct_member_callback);
2390 }
2391
2392 void register_comparison_inc_dec(int id)
2393 {
2394 inc_dec_id = id;
2395 add_modification_hook_late(inc_dec_id, &iter_modify);
2396 }
2397
2398 void register_comparison_inc_dec_links(int id)
2399 {
2400 inc_dec_link_id = id;
2401 set_up_link_functions(inc_dec_id, inc_dec_link_id);
2402 }
2403
2404 static void filter_by_sm(struct sm_state *sm, int op,
2405 struct state_list **true_stack,
2406 struct state_list **false_stack)
2407 {
2408 struct compare_data *data;
2409 int istrue = 0;
2410 int isfalse = 0;
2411
2412 if (!sm)
2413 return;
2414 data = sm->state->data;
2415 if (!data) {
2416 if (sm->merged) {
2417 filter_by_sm(sm->left, op, true_stack, false_stack);
2418 filter_by_sm(sm->right, op, true_stack, false_stack);
2419 }
2420 return;
2421 }
2422
2423 if (data->comparison &&
2424 data->comparison == filter_comparison(data->comparison, op))
2425 istrue = 1;
2426
2427 if (data->comparison &&
2428 data->comparison == filter_comparison(data->comparison, negate_comparison(op)))
2429 isfalse = 1;
2430
2431 if (istrue)
2432 add_ptr_list(true_stack, sm);
2433 if (isfalse)
2434 add_ptr_list(false_stack, sm);
2435
2436 if (sm->merged) {
2437 filter_by_sm(sm->left, op, true_stack, false_stack);
2438 filter_by_sm(sm->right, op, true_stack, false_stack);
2439 }
2440 }
2441
2442 struct sm_state *comparison_implication_hook(struct expression *expr,
2443 struct state_list **true_stack,
2444 struct state_list **false_stack)
2445 {
2446 struct sm_state *sm;
2447 char *left, *right;
2448 int op;
2449 static char buf[256];
2450
2451 if (expr->type != EXPR_COMPARE)
2452 return NULL;
2453
2454 op = expr->op;
2455
2456 left = expr_to_var(expr->left);
2457 right = expr_to_var(expr->right);
2458 if (!left || !right) {
2459 free_string(left);
2460 free_string(right);
2461 return NULL;
2462 }
2463
2464 if (strcmp(left, right) > 0) {
2465 char *tmp = left;
2466
2467 left = right;
2468 right = tmp;
2469 op = flip_comparison(op);
2470 }
2471
2472 snprintf(buf, sizeof(buf), "%s vs %s", left, right);
2473 sm = get_sm_state(compare_id, buf, NULL);
2474 if (!sm)
2475 return NULL;
2476 if (!sm->merged)
2477 return NULL;
2478
2479 filter_by_sm(sm, op, true_stack, false_stack);
2480 if (!*true_stack && !*false_stack)
2481 return NULL;
2482
2483 return sm;
2484 }
Static analysis for C