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