2 * sparse/smatch_states.c
4 * Copyright (C) 2006 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
13 #include "smatch_slist.h"
15 struct smatch_state undefined
= { .name
= "undefined" };
16 struct smatch_state true_state
= { .name
= "true" };
17 struct smatch_state false_state
= { .name
= "false" };
19 struct state_list
*cur_slist
; /* current states */
21 static struct state_list_stack
*true_stack
; /* states after a t/f branch */
22 static struct state_list_stack
*false_stack
;
23 static struct state_list_stack
*pre_cond_stack
; /* states before a t/f branch */
25 static struct state_list_stack
*cond_true_stack
; /* states affected by a branch */
26 static struct state_list_stack
*cond_false_stack
;
28 static struct state_list_stack
*break_stack
;
29 static struct state_list_stack
*switch_stack
;
30 static struct state_list_stack
*default_stack
;
31 static struct state_list_stack
*continue_stack
;
32 static struct state_list_stack
*false_only_stack
;
34 struct slist_stack
*goto_stack
;
38 void __print_slist(struct state_list
*slist
)
40 struct sm_state
*state
;
42 printf("dumping slist at %d\n", get_lineno());
43 FOR_EACH_PTR(slist
, state
) {
44 printf("'%s'=%s\n", state
->name
, show_state(state
->state
));
45 } END_FOR_EACH_PTR(state
);
49 void __print_cur_slist()
51 __print_slist(cur_slist
);
54 void set_state(const char *name
, int owner
, struct symbol
*sym
, struct smatch_state
*state
)
60 struct smatch_state
*s
;
62 s
= get_state(name
, owner
, sym
);
64 printf("%d new state. name='%s' owner=%d: %s\n",
65 get_lineno(), name
, owner
, show_state(state
));
67 printf("%d state change name='%s' owner=%d: %s => %s\n",
68 get_lineno(), name
, owner
, show_state(s
),
71 set_state_slist(&cur_slist
, name
, owner
, sym
, state
);
73 if (cond_true_stack
) {
74 set_state_stack(&cond_true_stack
, name
, owner
, sym
, state
);
75 set_state_stack(&cond_false_stack
, name
, owner
, sym
, state
);
79 struct smatch_state
*get_state(const char *name
, int owner
, struct symbol
*sym
)
81 return get_state_slist(cur_slist
, name
, owner
, sym
);
84 void delete_state(const char *name
, int owner
, struct symbol
*sym
)
86 delete_state_slist(&cur_slist
, name
, owner
, sym
);
89 struct state_list
*get_current_states(int owner
)
91 struct state_list
*slist
;
94 FOR_EACH_PTR(cur_slist
, tmp
) {
95 if (tmp
->owner
== owner
) {
96 add_ptr_list(&slist
, tmp
);
98 } END_FOR_EACH_PTR(tmp
);
103 void set_true_false_states(const char *name
, int owner
, struct symbol
*sym
,
104 struct smatch_state
*true_state
, struct smatch_state
*false_state
)
106 /* fixme. save history */
109 struct smatch_state
*tmp
;
111 tmp
= get_state(name
, owner
, sym
);
112 SM_DEBUG("%d set_true_false %s. Was %s. Now T:%s F:%s\n",
113 get_lineno(), name
, show_state(tmp
),
114 show_state(true_state
), show_state(false_state
));
117 if (!cond_false_stack
|| !cond_true_stack
) {
118 printf("Error: missing true/false stacks\n");
122 set_state_slist(&cur_slist
, name
, owner
, sym
, true_state
);
123 set_state_stack(&cond_true_stack
, name
, owner
, sym
, true_state
);
124 set_state_stack(&cond_false_stack
, name
, owner
, sym
, false_state
);
130 del_slist(&cur_slist
);
134 * At the start of every function we mark the path
135 * as unnull. That there is always at least one state
136 * in the cur_slist until nullify_path is called. This
137 * is used in merge_slist() for the first null check.
140 void __unnullify_path()
142 set_state("unnull_path", 0, NULL
, &true_state
);
145 void clear_all_states()
147 struct named_slist
*named_slist
;
150 del_slist_stack(&true_stack
);
151 del_slist_stack(&false_stack
);
152 del_slist_stack(&false_only_stack
);
153 del_slist_stack(&pre_cond_stack
);
154 del_slist_stack(&cond_true_stack
);
155 del_slist_stack(&cond_false_stack
);
156 del_slist_stack(&break_stack
);
157 del_slist_stack(&switch_stack
);
158 del_slist_stack(&continue_stack
);
160 FOR_EACH_PTR(goto_stack
, named_slist
) {
161 del_slist(&named_slist
->slist
);
162 } END_FOR_EACH_PTR(named_slist
);
163 __free_ptr_list((struct ptr_list
**)&goto_stack
);
167 void __push_cond_stacks()
169 push_slist(&cond_true_stack
, NULL
);
170 push_slist(&cond_false_stack
, NULL
);
174 * This combines the pre cond states with either the true or false states.
176 * a = kmalloc() ; if (a !! foo(a)
177 * In the pre state a is possibly null. In the true state it is non null.
178 * In the false state it is null. Combine the pre and the false to get
179 * that when we call 'foo', 'a' is null.
182 static void __use_cond_stack(struct state_list_stack
**stack
)
184 struct state_list
*slist
;
186 del_slist(&cur_slist
);
188 cur_slist
= pop_slist(&pre_cond_stack
);
189 push_slist(&pre_cond_stack
, clone_slist(cur_slist
));
191 slist
= pop_slist(stack
);
192 overwrite_slist(slist
, &cur_slist
);
193 push_slist(stack
, slist
);
197 void __use_cond_true_states()
199 __use_cond_stack(&cond_true_stack
);
202 void __use_cond_false_states()
204 __use_cond_stack(&cond_false_stack
);
207 void __negate_cond_stacks()
209 struct state_list
*old_false
, *old_true
;
211 old_false
= pop_slist(&cond_false_stack
);
212 old_true
= pop_slist(&cond_true_stack
);
214 overwrite_slist(old_false
, &cur_slist
);
216 push_slist(&cond_false_stack
, old_true
);
217 push_slist(&cond_true_stack
, old_false
);
221 void __and_cond_states()
223 struct state_list
*tmp_slist
;
225 tmp_slist
= pop_slist(&cond_true_stack
);
226 and_slist_stack(&cond_true_stack
, tmp_slist
);
227 or_slist_stack(&cond_false_stack
);
230 void __or_cond_states()
232 struct state_list
*tmp_slist
;
234 or_slist_stack(&cond_true_stack
);
235 tmp_slist
= pop_slist(&cond_false_stack
);
236 and_slist_stack(&cond_false_stack
, tmp_slist
);
240 void __save_pre_cond_states()
242 push_slist(&pre_cond_stack
, clone_slist(cur_slist
));
245 void __pop_pre_cond_states()
247 struct state_list
*tmp
;
249 tmp
= pop_slist(&pre_cond_stack
);
253 void __use_false_only_stack()
255 struct state_list
*slist
;
257 slist
= pop_slist(&false_only_stack
);
258 overwrite_slist(slist
, &cur_slist
);
262 void __pop_false_only_stack()
264 struct state_list
*slist
;
266 slist
= pop_slist(&false_only_stack
);
270 void __use_cond_states()
272 struct state_list
*pre
, *pre_clone
, *true_states
, *false_states
;
274 pre
= pop_slist(&pre_cond_stack
);
275 pre_clone
= clone_slist(pre
);
277 true_states
= pop_slist(&cond_true_stack
);
278 overwrite_slist(true_states
, &pre
);
279 /* we use the true states right away */
280 del_slist(&cur_slist
);
283 false_states
= pop_slist(&cond_false_stack
);
284 push_slist(&false_only_stack
, clone_slist(false_states
));
285 overwrite_slist(false_states
, &pre_clone
);
286 push_slist(&false_stack
, pre_clone
);
289 void __push_true_states()
291 push_slist(&true_stack
, clone_slist(cur_slist
));
294 void __use_false_states()
296 del_slist(&cur_slist
);
297 cur_slist
= pop_slist(&false_stack
);
300 void __pop_false_states()
302 struct state_list
*slist
;
304 slist
= pop_slist(&false_stack
);
308 void __merge_false_states()
310 struct state_list
*slist
;
312 slist
= pop_slist(&false_stack
);
313 merge_slist(&cur_slist
, slist
);
317 void __merge_true_states()
319 struct state_list
*slist
;
321 slist
= pop_slist(&true_stack
);
322 merge_slist(&cur_slist
, slist
);
326 void __push_continues()
328 push_slist(&continue_stack
, NULL
);
331 void __pop_continues()
333 struct state_list
*slist
;
335 slist
= pop_slist(&continue_stack
);
339 void __process_continues()
341 struct sm_state
*state
;
343 FOR_EACH_PTR(cur_slist
, state
) {
344 merge_state_stack(&continue_stack
, state
->name
, state
->owner
,
345 state
->sym
, state
->state
);
346 } END_FOR_EACH_PTR(state
);
349 void __merge_continues()
351 struct state_list
*slist
;
353 slist
= pop_slist(&continue_stack
);
354 merge_slist(&cur_slist
, slist
);
360 push_slist(&break_stack
, NULL
);
363 void __process_breaks()
365 struct state_list
*slist
;
367 slist
= pop_slist(&break_stack
);
370 overwrite_slist(cur_slist
, &slist
);
372 merge_slist(&slist
, cur_slist
);
374 push_slist(&break_stack
, slist
);
377 void __merge_breaks()
379 struct state_list
*slist
;
381 slist
= pop_slist(&break_stack
);
382 merge_slist(&cur_slist
, slist
);
388 del_slist(&cur_slist
);
389 cur_slist
= pop_slist(&break_stack
);
392 void __save_switch_states()
394 push_slist(&switch_stack
, clone_slist(cur_slist
));
397 void __merge_switches()
399 struct state_list
*slist
;
401 slist
= pop_slist(&switch_stack
);
402 merge_slist(&cur_slist
, slist
);
403 push_slist(&switch_stack
, slist
);
406 void __pop_switches()
408 struct state_list
*slist
;
410 slist
= pop_slist(&switch_stack
);
414 void __push_default()
416 push_slist(&default_stack
, NULL
);
421 set_state_stack(&default_stack
, "has_default", 0, NULL
, &true_state
);
426 struct state_list
*slist
;
428 slist
= pop_slist(&default_stack
);
436 static struct named_slist
*alloc_named_slist(const char *name
,
437 struct state_list
*slist
)
439 struct named_slist
*named_slist
= __alloc_named_slist(0);
441 named_slist
->name
= (char *)name
;
442 named_slist
->slist
= slist
;
446 void __save_gotos(const char *name
)
448 struct state_list
*slist
;
450 slist
= get_slist_from_slist_stack(goto_stack
, name
);
452 struct sm_state
*state
;
454 FOR_EACH_PTR(cur_slist
, state
) {
455 merge_state_slist(&slist
, state
->name
, state
->owner
,
456 state
->sym
, state
->state
);
457 } END_FOR_EACH_PTR(state
);
460 struct state_list
*slist
;
461 struct named_slist
*named_slist
;
463 slist
= clone_slist(cur_slist
);
464 named_slist
= alloc_named_slist(name
, slist
);
465 add_ptr_list(&goto_stack
, named_slist
);
469 void __merge_gotos(const char *name
)
471 struct state_list
*slist
;
473 slist
= get_slist_from_slist_stack(goto_stack
, name
);
475 merge_slist(&cur_slist
, slist
);