debug: update debug to handle the new comparison features
[smatch.git] / smatch_slist.c
blob7598be4ba2e9bfc406b478f79ae37a09f2ec52ef
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_slist.h"
15 #undef CHECKORDER
17 ALLOCATOR(smatch_state, "smatch state");
18 ALLOCATOR(sm_state, "sm state");
19 ALLOCATOR(named_slist, "named slist");
20 __DO_ALLOCATOR(char, 1, 4, "state names", sname);
22 static int sm_state_counter;
24 char *show_sm(struct sm_state *sm)
26 static char buf[256];
27 struct sm_state *tmp;
28 int pos;
29 int i;
31 pos = snprintf(buf, sizeof(buf), "[%s] '%s' = %s (",
32 check_name(sm->owner), sm->name, show_state(sm->state));
33 if (pos > sizeof(buf))
34 goto truncate;
36 i = 0;
37 FOR_EACH_PTR(sm->possible, tmp) {
38 if (i++)
39 pos += snprintf(buf + pos, sizeof(buf) - pos, ", ");
40 if (pos > sizeof(buf))
41 goto truncate;
42 pos += snprintf(buf + pos, sizeof(buf) - pos, "%s",
43 show_state(tmp->state));
44 if (pos > sizeof(buf))
45 goto truncate;
46 } END_FOR_EACH_PTR(tmp);
47 snprintf(buf + pos, sizeof(buf) - pos, ")");
49 return buf;
51 truncate:
52 for (i = 0; i < 3; i++)
53 buf[sizeof(buf) - 2 - i] = '.';
54 return buf;
57 void __print_slist(struct state_list *slist)
59 struct sm_state *sm;
61 printf("dumping slist at %d\n", get_lineno());
62 FOR_EACH_PTR(slist, sm) {
63 printf("%s\n", show_sm(sm));
64 } END_FOR_EACH_PTR(sm);
65 printf("---\n");
68 /* NULL states go at the end to simplify merge_slist */
69 int cmp_tracker(const struct sm_state *a, const struct sm_state *b)
71 int ret;
73 if (a == b)
74 return 0;
75 if (!b)
76 return -1;
77 if (!a)
78 return 1;
80 if (a->owner > b->owner)
81 return -1;
82 if (a->owner < b->owner)
83 return 1;
85 ret = strcmp(a->name, b->name);
86 if (ret)
87 return ret;
89 if (!b->sym && a->sym)
90 return -1;
91 if (!a->sym && b->sym)
92 return 1;
93 if (a->sym > b->sym)
94 return -1;
95 if (a->sym < b->sym)
96 return 1;
98 return 0;
101 static int cmp_sm_states(const struct sm_state *a, const struct sm_state *b)
103 int ret;
105 ret = cmp_tracker(a, b);
106 if (ret)
107 return ret;
109 /* todo: add hook for smatch_extra.c */
110 if (a->state > b->state)
111 return -1;
112 if (a->state < b->state)
113 return 1;
114 return 0;
117 static struct sm_state *alloc_sm_state(int owner, const char *name,
118 struct symbol *sym, struct smatch_state *state)
120 struct sm_state *sm_state = __alloc_sm_state(0);
122 sm_state_counter++;
124 sm_state->name = alloc_sname(name);
125 sm_state->owner = owner;
126 sm_state->sym = sym;
127 sm_state->state = state;
128 sm_state->line = get_lineno();
129 sm_state->merged = 0;
130 sm_state->implied = 0;
131 sm_state->pool = NULL;
132 sm_state->left = NULL;
133 sm_state->right = NULL;
134 sm_state->nr_children = 1;
135 sm_state->possible = NULL;
136 add_ptr_list(&sm_state->possible, sm_state);
137 return sm_state;
140 static struct sm_state *alloc_state_no_name(int owner, const char *name,
141 struct symbol *sym,
142 struct smatch_state *state)
144 struct sm_state *tmp;
146 tmp = alloc_sm_state(owner, NULL, sym, state);
147 tmp->name = name;
148 return tmp;
151 void add_sm_state_slist(struct state_list **slist, struct sm_state *new)
153 struct sm_state *tmp;
155 FOR_EACH_PTR(*slist, tmp) {
156 if (cmp_sm_states(tmp, new) < 0)
157 continue;
158 else if (cmp_sm_states(tmp, new) == 0) {
159 return;
160 } else {
161 INSERT_CURRENT(new, tmp);
162 return;
164 } END_FOR_EACH_PTR(tmp);
165 add_ptr_list(slist, new);
168 static void copy_possibles(struct sm_state *to, struct sm_state *from)
170 struct sm_state *tmp;
172 FOR_EACH_PTR(from->possible, tmp) {
173 add_sm_state_slist(&to->possible, tmp);
174 } END_FOR_EACH_PTR(tmp);
177 char *alloc_sname(const char *str)
179 char *tmp;
181 if (!str)
182 return NULL;
183 tmp = __alloc_sname(strlen(str) + 1);
184 strcpy(tmp, str);
185 return tmp;
188 int out_of_memory()
191 * I decided to use 50M here based on trial and error.
192 * It works out OK for the kernel and so it should work
193 * for most other projects as well.
195 if (sm_state_counter * sizeof(struct sm_state) >= 50000000)
196 return 1;
197 return 0;
200 int low_on_memory(void)
202 if (sm_state_counter * sizeof(struct sm_state) >= 25000000)
203 return 1;
204 return 0;
207 static void free_sm_state(struct sm_state *sm)
209 free_slist(&sm->possible);
211 * fixme. Free the actual state.
212 * Right now we leave it until the end of the function
213 * because we don't want to double free it.
214 * Use the freelist to not double free things
218 static void free_all_sm_states(struct allocation_blob *blob)
220 unsigned int size = sizeof(struct sm_state);
221 unsigned int offset = 0;
223 while (offset < blob->offset) {
224 free_sm_state((struct sm_state *)(blob->data + offset));
225 offset += size;
229 /* At the end of every function we free all the sm_states */
230 void free_every_single_sm_state(void)
232 struct allocator_struct *desc = &sm_state_allocator;
233 struct allocation_blob *blob = desc->blobs;
235 desc->blobs = NULL;
236 desc->allocations = 0;
237 desc->total_bytes = 0;
238 desc->useful_bytes = 0;
239 desc->freelist = NULL;
240 while (blob) {
241 struct allocation_blob *next = blob->next;
242 free_all_sm_states(blob);
243 blob_free(blob, desc->chunking);
244 blob = next;
246 clear_sname_alloc();
247 clear_smatch_state_alloc();
249 sm_state_counter = 0;
252 struct sm_state *clone_sm(struct sm_state *s)
254 struct sm_state *ret;
256 ret = alloc_state_no_name(s->owner, s->name, s->sym, s->state);
257 ret->merged = s->merged;
258 ret->implied = s->implied;
259 ret->line = s->line;
260 /* clone_sm() doesn't copy the pools. Each state needs to have
261 only one pool. */
262 ret->possible = clone_slist(s->possible);
263 ret->left = s->left;
264 ret->right = s->right;
265 ret->nr_children = s->nr_children;
266 return ret;
269 int is_merged(struct sm_state *sm)
271 return sm->merged;
274 int is_implied(struct sm_state *sm)
276 return sm->implied;
279 int slist_has_state(struct state_list *slist, struct smatch_state *state)
281 struct sm_state *tmp;
283 FOR_EACH_PTR(slist, tmp) {
284 if (tmp->state == state)
285 return 1;
286 } END_FOR_EACH_PTR(tmp);
287 return 0;
290 static void check_order(struct state_list *slist)
292 #ifdef CHECKORDER
293 struct sm_state *sm;
294 struct sm_state *last = NULL;
295 int printed = 0;
297 FOR_EACH_PTR(slist, sm) {
298 if (last && cmp_tracker(sm, last) <= 0) {
299 printf("Error. Unsorted slist %d vs %d, %p vs %p, "
300 "%s vs %s\n", last->owner, sm->owner,
301 last->sym, sm->sym, last->name, sm->name);
302 printed = 1;
304 last = sm;
305 } END_FOR_EACH_PTR(sm);
307 if (printed)
308 printf("======\n");
309 #endif
312 struct state_list *clone_slist(struct state_list *from_slist)
314 struct sm_state *sm;
315 struct state_list *to_slist = NULL;
317 FOR_EACH_PTR(from_slist, sm) {
318 add_ptr_list(&to_slist, sm);
319 } END_FOR_EACH_PTR(sm);
320 return to_slist;
323 struct state_list_stack *clone_stack(struct state_list_stack *from_stack)
325 struct state_list *slist;
326 struct state_list_stack *to_stack = NULL;
328 FOR_EACH_PTR(from_stack, slist) {
329 push_slist(&to_stack, slist);
330 } END_FOR_EACH_PTR(slist);
331 return to_stack;
334 struct smatch_state *merge_states(int owner, const char *name,
335 struct symbol *sym,
336 struct smatch_state *state1,
337 struct smatch_state *state2)
339 struct smatch_state *ret;
341 if (state1 == state2)
342 ret = state1;
343 else if (__has_merge_function(owner))
344 ret = __client_merge_function(owner, state1, state2);
345 else if (!state1 || !state2)
346 ret = &undefined;
347 else
348 ret = &merged;
349 return ret;
352 struct sm_state *merge_sm_states(struct sm_state *one, struct sm_state *two)
354 struct smatch_state *s;
355 struct sm_state *result;
357 if (one == two)
358 return one;
359 s = merge_states(one->owner, one->name, one->sym, one->state, two->state);
360 result = alloc_state_no_name(one->owner, one->name, one->sym, s);
361 result->merged = 1;
362 result->left = one;
363 result->right = two;
364 result->nr_children = one->nr_children + two->nr_children;
365 copy_possibles(result, one);
366 copy_possibles(result, two);
368 if (option_debug) {
369 struct sm_state *tmp;
370 int i = 0;
372 printf("%d merge [%s] '%s' %s(L %d) + %s(L %d) => %s (",
373 get_lineno(), check_name(one->owner), one->name,
374 show_state(one->state), one->line,
375 show_state(two->state), two->line,
376 show_state(s));
378 FOR_EACH_PTR(result->possible, tmp) {
379 if (i++)
380 printf(", ");
381 printf("%s", show_state(tmp->state));
382 } END_FOR_EACH_PTR(tmp);
383 printf(")\n");
386 return result;
389 struct sm_state *get_sm_state_slist(struct state_list *slist, int owner, const char *name,
390 struct symbol *sym)
392 struct sm_state *sm;
394 if (!name)
395 return NULL;
397 FOR_EACH_PTR(slist, sm) {
398 if (sm->owner == owner && sm->sym == sym && !strcmp(sm->name, name))
399 return sm;
400 } END_FOR_EACH_PTR(sm);
401 return NULL;
404 struct smatch_state *get_state_slist(struct state_list *slist,
405 int owner, const char *name,
406 struct symbol *sym)
408 struct sm_state *sm;
410 sm = get_sm_state_slist(slist, owner, name, sym);
411 if (sm)
412 return sm->state;
413 return NULL;
416 void overwrite_sm_state(struct state_list **slist, struct sm_state *new)
418 struct sm_state *tmp;
420 FOR_EACH_PTR(*slist, tmp) {
421 if (cmp_tracker(tmp, new) < 0)
422 continue;
423 else if (cmp_tracker(tmp, new) == 0) {
424 REPLACE_CURRENT_PTR(tmp, new);
425 return;
426 } else {
427 INSERT_CURRENT(new, tmp);
428 return;
430 } END_FOR_EACH_PTR(tmp);
431 add_ptr_list(slist, new);
434 void overwrite_sm_state_stack(struct state_list_stack **stack,
435 struct sm_state *sm)
437 struct state_list *slist;
439 slist = pop_slist(stack);
440 overwrite_sm_state(&slist, sm);
441 push_slist(stack, slist);
444 struct sm_state *set_state_slist(struct state_list **slist, int owner, const char *name,
445 struct symbol *sym, struct smatch_state *state)
447 struct sm_state *tmp;
448 struct sm_state *new = alloc_sm_state(owner, name, sym, state);
450 FOR_EACH_PTR(*slist, tmp) {
451 if (cmp_tracker(tmp, new) < 0)
452 continue;
453 else if (cmp_tracker(tmp, new) == 0) {
454 REPLACE_CURRENT_PTR(tmp, new);
455 return new;
456 } else {
457 INSERT_CURRENT(new, tmp);
458 return new;
460 } END_FOR_EACH_PTR(tmp);
461 add_ptr_list(slist, new);
462 return new;
465 void delete_state_slist(struct state_list **slist, int owner, const char *name,
466 struct symbol *sym)
468 struct sm_state *sm;
470 FOR_EACH_PTR(*slist, sm) {
471 if (sm->owner == owner && sm->sym == sym && !strcmp(sm->name, name)) {
472 DELETE_CURRENT_PTR(sm);
473 return;
475 } END_FOR_EACH_PTR(sm);
478 void delete_state_stack(struct state_list_stack **stack, int owner, const char *name,
479 struct symbol *sym)
481 struct state_list *slist;
483 slist = pop_slist(stack);
484 delete_state_slist(&slist, owner, name, sym);
485 push_slist(stack, slist);
488 void push_slist(struct state_list_stack **list_stack, struct state_list *slist)
490 add_ptr_list(list_stack, slist);
493 struct state_list *pop_slist(struct state_list_stack **list_stack)
495 struct state_list *slist;
497 slist = last_ptr_list((struct ptr_list *)*list_stack);
498 delete_ptr_list_last((struct ptr_list **)list_stack);
499 return slist;
502 void free_slist(struct state_list **slist)
504 __free_ptr_list((struct ptr_list **)slist);
507 void free_stack(struct state_list_stack **stack)
509 __free_ptr_list((struct ptr_list **)stack);
512 void free_stack_and_slists(struct state_list_stack **slist_stack)
514 struct state_list *slist;
516 FOR_EACH_PTR(*slist_stack, slist) {
517 free_slist(&slist);
518 } END_FOR_EACH_PTR(slist);
519 free_stack(slist_stack);
523 * set_state_stack() sets the state for the top slist on the stack.
525 struct sm_state *set_state_stack(struct state_list_stack **stack, int owner, const char *name,
526 struct symbol *sym, struct smatch_state *state)
528 struct state_list *slist;
529 struct sm_state *sm;
531 slist = pop_slist(stack);
532 sm = set_state_slist(&slist, owner, name, sym, state);
533 push_slist(stack, slist);
535 return sm;
539 * get_sm_state_stack() gets the state for the top slist on the stack.
541 struct sm_state *get_sm_state_stack(struct state_list_stack *stack,
542 int owner, const char *name,
543 struct symbol *sym)
545 struct state_list *slist;
546 struct sm_state *ret;
548 slist = pop_slist(&stack);
549 ret = get_sm_state_slist(slist, owner, name, sym);
550 push_slist(&stack, slist);
551 return ret;
554 struct smatch_state *get_state_stack(struct state_list_stack *stack,
555 int owner, const char *name,
556 struct symbol *sym)
558 struct sm_state *sm;
560 sm = get_sm_state_stack(stack, owner, name, sym);
561 if (sm)
562 return sm->state;
563 return NULL;
566 static void match_states(struct state_list **one, struct state_list **two)
568 struct sm_state *one_sm;
569 struct sm_state *two_sm;
570 struct sm_state *tmp;
571 struct smatch_state *tmp_state;
572 struct state_list *add_to_one = NULL;
573 struct state_list *add_to_two = NULL;
575 PREPARE_PTR_LIST(*one, one_sm);
576 PREPARE_PTR_LIST(*two, two_sm);
577 for (;;) {
578 if (!one_sm && !two_sm)
579 break;
580 if (cmp_tracker(one_sm, two_sm) < 0) {
581 __set_fake_cur_slist_fast(*two);
582 tmp_state = __client_unmatched_state_function(one_sm);
583 __pop_fake_cur_slist_fast();
584 tmp = alloc_state_no_name(one_sm->owner, one_sm->name,
585 one_sm->sym, tmp_state);
586 add_ptr_list(&add_to_two, tmp);
587 NEXT_PTR_LIST(one_sm);
588 } else if (cmp_tracker(one_sm, two_sm) == 0) {
589 NEXT_PTR_LIST(one_sm);
590 NEXT_PTR_LIST(two_sm);
591 } else {
592 __set_fake_cur_slist_fast(*one);
593 tmp_state = __client_unmatched_state_function(two_sm);
594 __pop_fake_cur_slist_fast();
595 tmp = alloc_state_no_name(two_sm->owner, two_sm->name,
596 two_sm->sym, tmp_state);
597 add_ptr_list(&add_to_one, tmp);
598 NEXT_PTR_LIST(two_sm);
601 FINISH_PTR_LIST(two_sm);
602 FINISH_PTR_LIST(one_sm);
604 overwrite_slist(add_to_one, one);
605 overwrite_slist(add_to_two, two);
608 static void clone_pool_havers(struct state_list *slist)
610 struct sm_state *sm;
611 struct sm_state *new;
613 FOR_EACH_PTR(slist, sm) {
614 if (sm->pool) {
615 new = clone_sm(sm);
616 REPLACE_CURRENT_PTR(sm, new);
618 } END_FOR_EACH_PTR(sm);
621 int __slist_id;
623 * Sets the first state to the slist_id.
625 static void set_slist_id(struct state_list *slist)
627 struct smatch_state *state;
628 struct sm_state *tmp, *new;
630 state = alloc_state_num(++__slist_id);
631 new = alloc_sm_state(-1, "unnull_path", NULL, state);
633 FOR_EACH_PTR(slist, tmp) {
634 if (tmp->owner != (unsigned short)-1)
635 return;
636 REPLACE_CURRENT_PTR(tmp, new);
637 return;
638 } END_FOR_EACH_PTR(tmp);
641 int get_slist_id(struct state_list *slist)
643 struct sm_state *tmp;
645 FOR_EACH_PTR(slist, tmp) {
646 if (tmp->owner != (unsigned short)-1)
647 return 0;
648 return PTR_INT(tmp->state->data);
649 } END_FOR_EACH_PTR(tmp);
650 return 0;
654 * merge_slist() is called whenever paths merge, such as after
655 * an if statement. It takes the two slists and creates one.
657 void merge_slist(struct state_list **to, struct state_list *slist)
659 struct sm_state *one_sm, *two_sm, *tmp;
660 struct state_list *results = NULL;
661 struct state_list *implied_one = NULL;
662 struct state_list *implied_two = NULL;
664 if (out_of_memory())
665 return;
667 check_order(*to);
668 check_order(slist);
670 /* merging a null and nonnull path gives you only the nonnull path */
671 if (!slist)
672 return;
674 if (!*to) {
675 *to = clone_slist(slist);
676 return;
679 implied_one = clone_slist(*to);
680 implied_two = clone_slist(slist);
682 match_states(&implied_one, &implied_two);
684 clone_pool_havers(implied_one);
685 clone_pool_havers(implied_two);
687 set_slist_id(implied_one);
688 set_slist_id(implied_two);
690 PREPARE_PTR_LIST(implied_one, one_sm);
691 PREPARE_PTR_LIST(implied_two, two_sm);
692 for (;;) {
693 if (!one_sm && !two_sm)
694 break;
695 if (cmp_tracker(one_sm, two_sm) < 0) {
696 sm_msg("error: Internal smatch error.");
697 NEXT_PTR_LIST(one_sm);
698 } else if (cmp_tracker(one_sm, two_sm) == 0) {
699 if (one_sm != two_sm) {
700 one_sm->pool = implied_one;
701 two_sm->pool = implied_two;
704 tmp = merge_sm_states(one_sm, two_sm);
705 add_ptr_list(&results, tmp);
706 NEXT_PTR_LIST(one_sm);
707 NEXT_PTR_LIST(two_sm);
708 } else {
709 sm_msg("error: Internal smatch error.");
710 NEXT_PTR_LIST(two_sm);
713 FINISH_PTR_LIST(two_sm);
714 FINISH_PTR_LIST(one_sm);
716 free_slist(to);
717 *to = results;
721 * filter_slist() removes any sm states "slist" holds in common with "filter"
723 void filter_slist(struct state_list **slist, struct state_list *filter)
725 struct sm_state *one_sm, *two_sm;
726 struct state_list *results = NULL;
728 PREPARE_PTR_LIST(*slist, one_sm);
729 PREPARE_PTR_LIST(filter, two_sm);
730 for (;;) {
731 if (!one_sm && !two_sm)
732 break;
733 if (cmp_tracker(one_sm, two_sm) < 0) {
734 add_ptr_list(&results, one_sm);
735 NEXT_PTR_LIST(one_sm);
736 } else if (cmp_tracker(one_sm, two_sm) == 0) {
737 if (one_sm != two_sm)
738 add_ptr_list(&results, one_sm);
739 NEXT_PTR_LIST(one_sm);
740 NEXT_PTR_LIST(two_sm);
741 } else {
742 NEXT_PTR_LIST(two_sm);
745 FINISH_PTR_LIST(two_sm);
746 FINISH_PTR_LIST(one_sm);
748 free_slist(slist);
749 *slist = results;
753 * and_slist_stack() pops the top two slists, overwriting the one with
754 * the other and pushing it back on the stack.
756 void and_slist_stack(struct state_list_stack **slist_stack)
758 struct sm_state *tmp;
759 struct state_list *right_slist = pop_slist(slist_stack);
761 FOR_EACH_PTR(right_slist, tmp) {
762 overwrite_sm_state_stack(slist_stack, tmp);
763 } END_FOR_EACH_PTR(tmp);
764 free_slist(&right_slist);
768 * or_slist_stack() is for if we have: if (foo || bar) { foo->baz;
769 * It pops the two slists from the top of the stack and merges them
770 * together in a way that preserves the things they have in common
771 * but creates a merged state for most of the rest.
772 * You could have code that had: if (foo || foo) { foo->baz;
773 * It's this function which ensures smatch does the right thing.
775 void or_slist_stack(struct state_list_stack **pre_conds,
776 struct state_list *cur_slist,
777 struct state_list_stack **slist_stack)
779 struct state_list *new;
780 struct state_list *old;
781 struct state_list *pre_slist;
782 struct state_list *res;
783 struct state_list *tmp_slist;
785 new = pop_slist(slist_stack);
786 old = pop_slist(slist_stack);
788 pre_slist = pop_slist(pre_conds);
789 push_slist(pre_conds, clone_slist(pre_slist));
791 res = clone_slist(pre_slist);
792 overwrite_slist(old, &res);
794 tmp_slist = clone_slist(cur_slist);
795 overwrite_slist(new, &tmp_slist);
797 merge_slist(&res, tmp_slist);
798 filter_slist(&res, pre_slist);
800 push_slist(slist_stack, res);
801 free_slist(&tmp_slist);
802 free_slist(&pre_slist);
803 free_slist(&new);
804 free_slist(&old);
808 * get_slist_from_named_stack() is only used for gotos.
810 struct state_list **get_slist_from_named_stack(struct named_stack *stack,
811 const char *name)
813 struct named_slist *tmp;
815 FOR_EACH_PTR(stack, tmp) {
816 if (!strcmp(tmp->name, name))
817 return &tmp->slist;
818 } END_FOR_EACH_PTR(tmp);
819 return NULL;
822 void overwrite_slist(struct state_list *from, struct state_list **to)
824 struct sm_state *tmp;
826 FOR_EACH_PTR(from, tmp) {
827 overwrite_sm_state(to, tmp);
828 } END_FOR_EACH_PTR(tmp);