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