Merge branch 'master' into null_deref
[smatch.git] / smatch_slist.c
blob54194db46f7d685eba0d1ccce7294d5ce8fa87b2
1 /*
2 * sparse/smatch_slist.c
4 * Copyright (C) 2008,2009 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
8 */
10 #include <stdlib.h>
11 #include <stdio.h>
12 #include "smatch.h"
13 #include "smatch.h"
14 #include "smatch_slist.h"
16 ALLOCATOR(sm_state, "smatch state");
17 ALLOCATOR(named_slist, "named slist");
19 #undef CHECKORDER
21 void __print_slist(struct state_list *slist)
23 struct sm_state *state;
25 printf("dumping slist at %d\n", get_lineno());
26 FOR_EACH_PTR(slist, state) {
27 printf("%d '%s'=%s\n", state->owner, state->name,
28 show_state(state->state));
29 } END_FOR_EACH_PTR(state);
30 printf("---\n");
33 void add_history(struct sm_state *state)
35 struct state_history *tmp;
37 if (!state)
38 return;
39 tmp = malloc(sizeof(*tmp));
40 tmp->loc = get_lineno();
41 add_ptr_list(&state->line_history, tmp);
44 static void add_possible(struct sm_state *sm, struct sm_state *new)
46 struct sm_state *tmp;
48 FOR_EACH_PTR(sm->possible, tmp) {
49 if (tmp->state < new->state) {
50 continue;
51 } else if (tmp->state == new->state) {
52 return;
53 } else {
54 INSERT_CURRENT(new, tmp);
55 return;
57 } END_FOR_EACH_PTR(tmp);
58 add_ptr_list(&sm->possible, new);
61 struct sm_state *alloc_state(const char *name, int owner,
62 struct symbol *sym, struct smatch_state *state)
64 struct sm_state *sm_state = __alloc_sm_state(0);
66 sm_state->name = (char *)name;
67 sm_state->owner = owner;
68 sm_state->sym = sym;
69 sm_state->state = state;
70 sm_state->line_history = NULL;
71 add_history(sm_state);
72 sm_state->pools = NULL;
73 sm_state->possible = NULL;
74 add_possible(sm_state, sm_state);
75 return sm_state;
78 struct sm_state *clone_state(struct sm_state *s)
80 struct sm_state *tmp;
82 tmp = alloc_state(s->name, s->owner, s->sym, s->state);
83 tmp->pools = clone_stack(s->pools);
84 return tmp;
87 /* NULL states go at the end to simplify merge_slist */
88 static int cmp_sm_states(const struct sm_state *a, const struct sm_state *b)
90 int ret;
92 if (!a && !b)
93 return 0;
94 if (!b)
95 return -1;
96 if (!a)
97 return 1;
99 if (a->owner > b->owner)
100 return -1;
101 if (a->owner < b->owner)
102 return 1;
104 ret = strcmp(a->name, b->name);
105 if (ret)
106 return ret;
108 if (!b->sym && a->sym)
109 return -1;
110 if (!a->sym && b->sym)
111 return 1;
112 if (a->sym > b->sym)
113 return -1;
114 if (a->sym < b->sym)
115 return 1;
117 return 0;
120 int slist_has_state(struct state_list *slist, struct smatch_state *state)
122 struct sm_state *tmp;
124 FOR_EACH_PTR(slist, tmp) {
125 if (tmp->state == state)
126 return 1;
127 } END_FOR_EACH_PTR(tmp);
128 return 0;
131 #ifdef CHECKORDER
132 static void check_order(struct state_list *slist)
134 struct sm_state *state;
135 struct sm_state *last = NULL;
136 int printed = 0;
138 FOR_EACH_PTR(slist, state) {
139 if (last && cmp_sm_states(state, last) <= 0) {
140 printf("Error. Unsorted slist %d vs %d, %p vs %p, "
141 "%s vs %s\n", last->owner, state->owner,
142 last->sym, state->sym, last->name, state->name);
143 printed = 1;
145 last = state;
146 } END_FOR_EACH_PTR(state);
148 if (printed)
149 printf("======\n");
151 #endif
153 struct state_list *clone_slist(struct state_list *from_slist)
155 struct sm_state *state;
156 struct sm_state *tmp;
157 struct state_list *to_slist = NULL;
159 FOR_EACH_PTR(from_slist, state) {
160 tmp = clone_state(state);
161 add_ptr_list(&to_slist, tmp);
162 } END_FOR_EACH_PTR(state);
163 #ifdef CHECKORDER
164 check_order(to_slist);
165 #endif
166 return to_slist;
169 struct state_list_stack *clone_stack(struct state_list_stack *from_stack)
171 struct state_list *slist;
172 struct state_list_stack *to_stack = NULL;
174 FOR_EACH_PTR(from_stack, slist) {
175 push_slist(&to_stack, slist);
176 } END_FOR_EACH_PTR(slist);
177 return to_stack;
180 // FIXME... shouldn't we free some of these state pointers?
181 struct smatch_state *merge_states(const char *name, int owner,
182 struct symbol *sym,
183 struct smatch_state *state1,
184 struct smatch_state *state2)
186 struct smatch_state *ret;
188 if (state1 == state2)
189 ret = state1;
190 else if (__has_merge_function(owner))
191 ret = __client_merge_function(owner, name, sym, state1, state2);
192 else
193 ret = &merged;
195 SM_DEBUG("%d merge name='%s' owner=%d: %s + %s => %s\n",
196 get_lineno(), name, owner, show_state(state1),
197 show_state(state2), show_state(ret));
199 return ret;
202 struct sm_state *get_sm_state_slist(struct state_list *slist, const char *name,
203 int owner, struct symbol *sym)
205 struct sm_state *state;
207 if (!name)
208 return NULL;
210 FOR_EACH_PTR(slist, state) {
211 if (state->owner == owner && state->sym == sym
212 && !strcmp(state->name, name))
213 return state;
214 } END_FOR_EACH_PTR(state);
215 return NULL;
218 struct smatch_state *get_state_slist(struct state_list *slist,
219 const char *name, int owner,
220 struct symbol *sym)
222 struct sm_state *state;
224 state = get_sm_state_slist(slist, name, owner, sym);
225 if (state)
226 return state->state;
227 return NULL;
230 static void overwrite_sm_state(struct state_list **slist,
231 struct sm_state *state)
233 struct sm_state *tmp;
234 struct sm_state *new = clone_state(state); //fixme. why?
236 FOR_EACH_PTR(*slist, tmp) {
237 if (cmp_sm_states(tmp, new) < 0)
238 continue;
239 else if (cmp_sm_states(tmp, new) == 0) {
240 tmp->state = new->state;
241 tmp->pools = new->pools;
242 tmp->possible = new->possible;
243 __free_sm_state(new);
244 return;
245 } else {
246 INSERT_CURRENT(new, tmp);
247 return;
249 } END_FOR_EACH_PTR(tmp);
250 add_ptr_list(slist, new);
253 void set_state_slist(struct state_list **slist, const char *name, int owner,
254 struct symbol *sym, struct smatch_state *state)
256 struct sm_state *tmp;
257 struct sm_state *new = alloc_state(name, owner, sym, state);
259 FOR_EACH_PTR(*slist, tmp) {
260 if (cmp_sm_states(tmp, new) < 0)
261 continue;
262 else if (cmp_sm_states(tmp, new) == 0) {
263 tmp->state = state;
264 tmp->pools = NULL;
265 tmp->possible = NULL;
266 __free_sm_state(new);
267 return;
268 } else {
269 INSERT_CURRENT(new, tmp);
270 return;
272 } END_FOR_EACH_PTR(tmp);
273 add_ptr_list(slist, new);
276 void delete_state_slist(struct state_list **slist, const char *name, int owner,
277 struct symbol *sym)
279 struct sm_state *state;
281 FOR_EACH_PTR(*slist, state) {
282 if (state->owner == owner && state->sym == sym
283 && !strcmp(state->name, name)){
284 delete_ptr_list_entry((struct ptr_list **)slist,
285 state, 1);
286 __free_sm_state(state);
287 return;
289 } END_FOR_EACH_PTR(state);
293 void push_slist(struct state_list_stack **list_stack, struct state_list *slist)
295 add_ptr_list(list_stack, slist);
298 struct state_list *pop_slist(struct state_list_stack **list_stack)
300 struct state_list *slist;
302 slist = last_ptr_list((struct ptr_list *)*list_stack);
303 delete_ptr_list_last((struct ptr_list **)list_stack);
304 return slist;
307 void del_slist(struct state_list **slist)
309 __free_ptr_list((struct ptr_list **)slist);
312 void del_slist_stack(struct state_list_stack **slist_stack)
314 struct state_list *slist;
316 FOR_EACH_PTR(*slist_stack, slist) {
317 __free_ptr_list((struct ptr_list **)&slist);
318 } END_FOR_EACH_PTR(slist);
319 __free_ptr_list((struct ptr_list **)slist_stack);
323 * set_state_stack() sets the state for the top slist on the stack.
325 void set_state_stack(struct state_list_stack **stack, const char *name,
326 int owner, struct symbol *sym, struct smatch_state *state)
328 struct state_list *slist;
330 slist = pop_slist(stack);
331 set_state_slist(&slist, name, owner, sym, state);
332 push_slist(stack, slist);
336 * get_state_stack() gets the state for the top slist on the stack.
338 struct smatch_state *get_state_stack(struct state_list_stack *stack,
339 const char *name, int owner,
340 struct symbol *sym)
342 struct state_list *slist;
343 struct smatch_state *ret;
345 slist = pop_slist(&stack);
346 ret = get_state_slist(slist, name, owner, sym);
347 push_slist(&stack, slist);
348 return ret;
352 * add_pool() adds a slist to ->pools. If the slist has already been
353 * added earlier then it doesn't get added a second time.
355 static void add_pool(struct sm_state *to, struct state_list *new)
357 struct state_list *tmp;
359 FOR_EACH_PTR(to->pools, tmp) {
360 if (tmp < new)
361 continue;
362 else if (tmp == new) {
363 return;
364 } else {
365 INSERT_CURRENT(new, tmp);
366 return;
368 } END_FOR_EACH_PTR(tmp);
369 add_ptr_list(&to->pools, new);
372 static void copy_pools(struct sm_state *to, struct sm_state *sm)
374 struct state_list *tmp;
376 FOR_EACH_PTR(sm->pools, tmp) {
377 add_pool(to, tmp);
378 } END_FOR_EACH_PTR(tmp);
382 * merge_slist() is called whenever paths merge, such as after
383 * an if statement. It takes the two slists and creates one.
385 void merge_slist(struct state_list **to, struct state_list *slist)
387 struct sm_state *to_state, *state, *tmp;
388 struct state_list *results = NULL;
389 struct smatch_state *s;
390 struct state_list *implied_to = NULL;
391 struct state_list *implied_from = NULL;
393 #ifdef CHECKORDER
394 check_order(*to);
395 check_order(slist);
396 #endif
398 /* merging a null and nonnull path gives you only the nonnull path */
399 if (!slist) {
400 return;
402 if (!*to) {
403 *to = clone_slist(slist);
404 return;
407 PREPARE_PTR_LIST(*to, to_state);
408 PREPARE_PTR_LIST(slist, state);
409 for (;;) {
410 if (!to_state && !state)
411 break;
412 if (cmp_sm_states(to_state, state) < 0) {
413 s = merge_states(to_state->name, to_state->owner,
414 to_state->sym, to_state->state, NULL);
415 tmp = alloc_state(to_state->name, to_state->owner,
416 to_state->sym, s);
417 copy_pools(tmp, to_state);
419 add_ptr_list(&implied_to, to_state);
420 add_pool(tmp, implied_to);
422 add_ptr_list(&results, tmp);
423 NEXT_PTR_LIST(to_state);
424 } else if (cmp_sm_states(to_state, state) == 0) {
425 if (to_state->state == state->state) {
426 s = to_state->state;
427 tmp = alloc_state(to_state->name,
428 to_state->owner,
429 to_state->sym, s);
430 copy_pools(tmp, to_state);
431 copy_pools(tmp, state);
433 } else {
434 s = merge_states(to_state->name,
435 to_state->owner,
436 to_state->sym, to_state->state,
437 state->state);
439 tmp = alloc_state(to_state->name,
440 to_state->owner,
441 to_state->sym, s);
442 copy_pools(tmp, to_state);
443 copy_pools(tmp, state);
445 add_possible(tmp, state);
446 add_possible(tmp, to_state);
448 add_ptr_list(&implied_to, to_state);
449 add_pool(tmp, implied_to);
451 add_ptr_list(&implied_from, state);
452 add_pool(tmp, implied_from);
454 add_ptr_list(&results, tmp);
455 NEXT_PTR_LIST(to_state);
456 NEXT_PTR_LIST(state);
457 } else {
458 s = merge_states(state->name, state->owner,
459 state->sym, state->state, NULL);
460 tmp = alloc_state(state->name, state->owner,
461 state->sym, s);
462 copy_pools(tmp, state);
464 add_ptr_list(&implied_from, state);
465 add_pool(tmp, implied_from);
467 add_ptr_list(&results, tmp);
468 NEXT_PTR_LIST(state);
471 FINISH_PTR_LIST(state);
472 FINISH_PTR_LIST(to_state);
474 del_slist(to);
475 *to = results;
477 if (implied_from)
478 push_slist(&implied_pools, implied_from);
479 if (implied_to)
480 push_slist(&implied_pools, implied_to);
484 * is_currently_in_pool() is used because we remove states from pools.
485 * When set_state() is called then we set ->pools to NULL, but on
486 * other paths the state is still a member of those pools.
487 * Confusing huh?
488 * if (foo) {
489 * bar = 1;
490 * a = malloc();
492 * if (!a)
493 * return;
494 * if (bar)
495 * a->b = x;
497 static int is_currently_in_pool(struct sm_state *sm, struct state_list *pool,
498 struct state_list *cur_slist)
500 struct sm_state *cur_state;
501 struct state_list *tmp;
503 cur_state = get_sm_state_slist(cur_slist, sm->name, sm->owner, sm->sym);
504 if (!cur_state)
505 return 0;
507 FOR_EACH_PTR(cur_state->pools, tmp) {
508 if (tmp == pool)
509 return 1;
510 } END_FOR_EACH_PTR(tmp);
511 return 0;
514 struct state_list *clone_states_in_pool(struct state_list *pool,
515 struct state_list *cur_slist)
517 struct sm_state *state;
518 struct sm_state *tmp;
519 struct state_list *to_slist = NULL;
521 FOR_EACH_PTR(pool, state) {
522 if (is_currently_in_pool(state, pool, cur_slist)) {
523 tmp = clone_state(state);
524 add_ptr_list(&to_slist, tmp);
526 } END_FOR_EACH_PTR(state);
527 #ifdef CHECKORDER
528 check_order(to_slist);
529 #endif
530 return to_slist;
534 * filter() is used to find what states are the same across
535 * a series of slists.
536 * It takes a **slist and a *filter.
537 * It removes everything from **slist that isn't in *filter.
538 * The reason you would want to do this is if you want to
539 * know what other states are true if one state is true. (smatch_implied).
541 void filter(struct state_list **slist, struct state_list *filter,
542 struct state_list *cur_slist)
544 struct sm_state *s_one, *s_two;
545 struct state_list *results = NULL;
547 #ifdef CHECKORDER
548 check_order(*slist);
549 check_order(filter);
550 #endif
552 PREPARE_PTR_LIST(*slist, s_one);
553 PREPARE_PTR_LIST(filter, s_two);
554 for (;;) {
555 if (!s_one || !s_two)
556 break;
557 if (cmp_sm_states(s_one, s_two) < 0) {
558 NEXT_PTR_LIST(s_one);
559 } else if (cmp_sm_states(s_one, s_two) == 0) {
560 /* todo. pointer comparison works fine for most things
561 except smatch_extra. we may need a hook here. */
562 if (s_one->state == s_two->state &&
563 is_currently_in_pool(s_two, filter, cur_slist)) {
564 add_ptr_list(&results, s_one);
566 NEXT_PTR_LIST(s_one);
567 NEXT_PTR_LIST(s_two);
568 } else {
569 NEXT_PTR_LIST(s_two);
572 FINISH_PTR_LIST(s_two);
573 FINISH_PTR_LIST(s_one);
575 del_slist(slist);
576 *slist = results;
580 * and_slist_stack() is basically the same as popping the top two slists,
581 * overwriting the one with the other and pushing it back on the stack.
582 * The difference is that it checks to see that a mutually exclusive
583 * state isn't included in both stacks. If smatch sees something like
584 * "if (a && !a)" it prints a warning.
586 void and_slist_stack(struct state_list_stack **slist_stack)
588 struct sm_state *tmp;
589 struct smatch_state *tmp_state;
590 struct state_list *tmp_slist = pop_slist(slist_stack);
592 FOR_EACH_PTR(tmp_slist, tmp) {
593 tmp_state = get_state_stack(*slist_stack, tmp->name,
594 tmp->owner, tmp->sym);
595 if (tmp_state && tmp_state != tmp->state) {
596 smatch_msg("mutually exclusive 'and' conditions states "
597 "'%s': %s & %s.\n",
598 tmp->name, show_state(tmp_state),
599 show_state(tmp->state));
600 tmp->state = merge_states(tmp->name, tmp->owner,
601 tmp->sym, tmp->state,
602 tmp_state);
604 set_state_stack(slist_stack, tmp->name, tmp->owner, tmp->sym,
605 tmp->state);
606 } END_FOR_EACH_PTR(tmp);
607 del_slist(&tmp_slist);
611 * or_slist_stack() is for if we have: if (foo || bar) { foo->baz;
612 * It pops the two slists from the top of the stack and merges them
613 * together in a way that preserves the things they have in common
614 * but creates a merged state for most of the rest.
615 * You could have code that had: if (foo || foo) { foo->baz;
616 * It's this function which ensures smatch does the right thing.
618 void or_slist_stack(struct state_list_stack **slist_stack)
620 struct state_list *one;
621 struct state_list *two;
622 struct state_list *res = NULL;
623 struct sm_state *tmp;
624 struct smatch_state *s;
626 one = pop_slist(slist_stack);
627 two = pop_slist(slist_stack);
629 FOR_EACH_PTR(one, tmp) {
630 s = get_state_slist(two, tmp->name, tmp->owner, tmp->sym);
631 s = merge_states(tmp->name, tmp->owner, tmp->sym,
632 tmp->state, s);
633 set_state_slist(&res, tmp->name, tmp->owner, tmp->sym, s);
634 } END_FOR_EACH_PTR(tmp);
636 FOR_EACH_PTR(two, tmp) {
637 s = get_state_slist(one, tmp->name, tmp->owner, tmp->sym);
638 s = merge_states(tmp->name, tmp->owner, tmp->sym,
639 tmp->state, s);
640 set_state_slist(&res, tmp->name, tmp->owner, tmp->sym, s);
641 } END_FOR_EACH_PTR(tmp);
643 push_slist(slist_stack, res);
645 del_slist(&one);
646 del_slist(&two);
650 * get_slist_from_named_stack() is only used for gotos.
652 struct state_list **get_slist_from_named_stack(struct named_stack *stack,
653 const char *name)
655 struct named_slist *tmp;
657 FOR_EACH_PTR(stack, tmp) {
658 if (!strcmp(tmp->name, name))
659 return &tmp->slist;
660 } END_FOR_EACH_PTR(tmp);
661 return NULL;
664 void overwrite_slist(struct state_list *from, struct state_list **to)
666 struct sm_state *tmp;
668 FOR_EACH_PTR(from, tmp) {
669 overwrite_sm_state(to, tmp);
670 } END_FOR_EACH_PTR(tmp);