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