2 * sparse/smatch_states.c
4 * Copyright (C) 2006 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
14 ALLOCATOR(smatch_state
, "smatch state");
15 DECLARE_PTR_LIST(state_list
, struct smatch_state
);
16 DECLARE_PTR_LIST(state_list_stack
, struct state_list
);
18 static struct state_list
*cur_slist
;
19 static struct state_list_stack
*false_stack
;
20 static struct state_list_stack
*true_stack
;
21 static struct state_list_stack
*break_stack
;
22 static struct state_list_stack
*switch_stack
;
23 static struct state_list_stack
*default_stack
;
24 static struct state_list_stack
*continue_stack
;
25 static struct state_list_stack
*mini_false_stack
;
26 static struct state_list
*and_clumps
[2];
30 struct state_list
*slist
;
32 ALLOCATOR(slist_head
, "goto stack");
33 DECLARE_PTR_LIST(slist_stack
, struct slist_head
);
34 static struct slist_stack
*goto_stack
;
38 void __print_cur_slist()
40 struct smatch_state
*state
;
42 printf("dumping slist at %d\n", get_lineno());
43 FOR_EACH_PTR(cur_slist
, state
) {
44 printf("%s=%d\n", state
->name
, state
->state
);
45 } END_FOR_EACH_PTR(state
);
49 static void add_history(struct smatch_state
*state
)
51 struct state_history
*tmp
;
55 tmp
= malloc(sizeof(*tmp
));
56 tmp
->loc
= get_lineno();
57 add_ptr_list(&state
->line_history
, tmp
);
58 tmp
= malloc(sizeof(*tmp
));
59 tmp
->loc
= get_path_id();
60 add_ptr_list(&state
->line_history
, tmp
);
63 struct smatch_state
*alloc_state(const char *name
, int owner
,
64 struct symbol
*sym
, int state
)
66 struct smatch_state
*sm_state
= __alloc_smatch_state(0);
68 sm_state
->name
= (char *)name
;
69 sm_state
->owner
= owner
;
71 sm_state
->state
= state
;
72 sm_state
->line_history
= NULL
;
73 sm_state
->path_history
= NULL
;
74 add_history(sm_state
);
78 static struct smatch_state
*clone_state(struct smatch_state
*s
)
80 return alloc_state(s
->name
, s
->owner
, s
->sym
, s
->state
);
83 static void push_slist(struct state_list_stack
**list_stack
,
84 struct state_list
*slist
)
86 add_ptr_list(list_stack
, slist
);
89 static struct state_list
*pop_slist(struct state_list_stack
**list_stack
)
91 struct state_list
*slist
;
93 slist
= last_ptr_list((struct ptr_list
*)*list_stack
);
94 delete_ptr_list_entry((struct ptr_list
**)list_stack
, slist
, 1);
98 static struct state_list
*clone_slist(struct state_list
*from_slist
)
100 struct smatch_state
*state
;
101 struct smatch_state
*tmp
;
102 struct state_list
*to_slist
= NULL
;
104 FOR_EACH_PTR(from_slist
, state
) {
105 tmp
= clone_state(state
);
106 add_ptr_list(&to_slist
, tmp
);
107 } END_FOR_EACH_PTR(state
);
111 static void del_slist(struct state_list
**slist
)
113 __free_ptr_list((struct ptr_list
**)slist
);
116 static void del_slist_stack(struct state_list_stack
**slist_stack
)
118 struct state_list
*slist
;
120 FOR_EACH_PTR(*slist_stack
, slist
) {
121 __free_ptr_list((struct ptr_list
**)&slist
);
122 } END_FOR_EACH_PTR(slist
);
123 __free_ptr_list((struct ptr_list
**)slist_stack
);
126 static void add_state_slist(struct state_list
**slist
,
127 struct smatch_state
*state
)
129 add_ptr_list(slist
, state
);
132 static void set_state_slist(struct state_list
**slist
, const char *name
,
133 int owner
, struct symbol
*sym
, int state
)
135 struct smatch_state
*tmp
;
137 FOR_EACH_PTR(*slist
, tmp
) {
138 if (tmp
->owner
== owner
&& tmp
->sym
== sym
139 && !strcmp(tmp
->name
, name
)){
143 } END_FOR_EACH_PTR(tmp
);
144 tmp
= alloc_state(name
, owner
, sym
, state
);
145 add_state_slist(slist
, tmp
);
148 static inline void set_state_stack(struct state_list_stack
**stack
,
149 const char *name
, int owner
,
150 struct symbol
*sym
, int state
)
152 struct state_list
*slist
;
154 slist
= pop_slist(stack
);
155 set_state_slist(&slist
, name
, owner
, sym
, state
);
156 push_slist(stack
, slist
);
159 static int merge_states(const char *name
, int owner
, struct symbol
*sym
,
160 int state1
, int state2
)
165 if (state1
== state2
)
167 else if (__has_merge_function(owner
))
168 ret
= __client_merge_function(owner
, name
, sym
, (state1
< state2
?state1
:state2
), (state1
> state2
?state1
:state2
));
172 SM_DEBUG("%d merge name='%s' owner=%d: %d + %d => %d\n",
173 get_lineno(), name
, owner
, state1
, state2
, ret
);
178 static void merge_state_slist(struct state_list
**slist
, const char *name
,
179 int owner
, struct symbol
*sym
, int state
)
181 struct smatch_state
*tmp
;
184 FOR_EACH_PTR(*slist
, tmp
) {
185 if (tmp
->owner
== owner
&& tmp
->sym
== sym
186 && !strcmp(tmp
->name
, name
)){
187 s
= merge_states(name
, owner
, sym
, tmp
->state
, state
);
188 if (tmp
->state
!= s
) {
194 } END_FOR_EACH_PTR(tmp
);
195 tmp
= alloc_state(name
, owner
, sym
, state
);
196 add_state_slist(slist
, tmp
);
199 static void merge_state_stack(struct state_list_stack
** stack
,
200 const char *name
, int owner
, struct symbol
*sym
,
203 struct state_list
*slist
;
205 slist
= pop_slist(stack
);
206 merge_state_slist(&slist
, name
, owner
, sym
, state
);
207 push_slist(stack
, slist
);
210 static void delete_state_slist(struct state_list
**slist
, const char *name
,
211 int owner
, struct symbol
*sym
)
213 struct smatch_state
*state
;
215 FOR_EACH_PTR(*slist
, state
) {
216 if (state
->owner
== owner
&& state
->sym
== sym
217 && !strcmp(state
->name
, name
)){
218 delete_ptr_list_entry((struct ptr_list
**)slist
,
220 __free_smatch_state(state
);
223 } END_FOR_EACH_PTR(state
);
226 static void merge_slist(struct state_list
*slist
)
228 struct smatch_state
*state
;
229 FOR_EACH_PTR(slist
, state
) {
230 merge_state_slist(&cur_slist
, state
->name
, state
->owner
,
231 state
->sym
, state
->state
);
232 } END_FOR_EACH_PTR(state
);
235 void set_state(const char *name
, int owner
, struct symbol
*sym
, int state
)
237 struct smatch_state
*tmp
;
242 FOR_EACH_PTR(cur_slist
, tmp
) {
243 if (tmp
->owner
== owner
&& tmp
->sym
== sym
244 && !strcmp(tmp
->name
, name
)){
245 SM_DEBUG("%d state change name='%s' owner=%d: %d => %d\n"
246 , get_lineno(), name
, owner
, tmp
->state
, state
);
251 } END_FOR_EACH_PTR(tmp
);
252 SM_DEBUG("%d new state. name='%s' owner=%d: %d\n", get_lineno(), name
,
254 tmp
= alloc_state(name
, owner
, sym
, state
);
255 add_state_slist(&cur_slist
, tmp
);
259 static int get_state_slist(struct state_list
*slist
, const char *name
,
260 int owner
, struct symbol
*sym
)
262 struct smatch_state
*state
;
267 FOR_EACH_PTR(cur_slist
, state
) {
268 if (state
->owner
== owner
&& state
->sym
== sym
269 && !strcmp(state
->name
, name
))
271 } END_FOR_EACH_PTR(state
);
275 int get_state(const char *name
, int owner
, struct symbol
*sym
)
277 return get_state_slist(cur_slist
, name
, owner
, sym
);
280 struct state_list
*get_current_states(int owner
)
282 struct state_list
*slist
;
283 struct smatch_state
*tmp
;
285 FOR_EACH_PTR(cur_slist
, tmp
) {
286 if (tmp
->owner
== owner
) {
287 add_ptr_list(&slist
, tmp
);
289 } END_FOR_EACH_PTR(tmp
);
294 void set_true_false_states(const char *name
, int owner
, struct symbol
*sym
,
295 int true_state
, int false_state
)
297 int merged
= merge_states(name
, owner
, sym
, true_state
, false_state
);
299 /* fixme. history plus don't call get_state() when not needed*/
300 //SM_DEBUG("%d set_true_false %s. Was %d. Now T:%d F:%d\n",
301 // get_lineno(), name, get_state(name, owner, sym), true_state,
304 if (!false_stack
|| !true_stack
|| !mini_false_stack
) {
305 printf("Error: missing true/false stacks\n");
309 int tmp
= true_state
;
311 true_state
= false_state
;
314 set_state(name
, owner
, sym
, true_state
);
315 set_state_stack(&mini_false_stack
, name
, owner
, sym
, false_state
);
316 set_state_slist(&and_clumps
[1], name
, owner
, sym
, true_state
);
317 set_state_stack(&true_stack
, name
, owner
, sym
,
318 (__ors
?merged
:true_state
));
319 set_state_stack(&false_stack
, name
, owner
, sym
,
320 (__ands
?merged
:false_state
));
323 void delete_state(const char *name
, int owner
, struct symbol
*sym
)
325 delete_state_slist(&cur_slist
, name
, owner
, sym
);
330 del_slist(&cur_slist
);
333 void clear_all_states()
335 struct slist_head
*slist_head
;
338 del_slist_stack(&false_stack
);
339 del_slist_stack(&true_stack
);
340 del_slist_stack(&break_stack
);
341 del_slist_stack(&switch_stack
);
342 del_slist_stack(&continue_stack
);
343 del_slist_stack(&mini_false_stack
);
344 del_slist(&and_clumps
[0]);
345 del_slist(&and_clumps
[1]);
347 FOR_EACH_PTR(goto_stack
, slist_head
) {
348 del_slist(&slist_head
->slist
);
349 } END_FOR_EACH_PTR(slist_head
);
350 __free_ptr_list((struct ptr_list
**)&goto_stack
);
353 void __first_and_clump()
355 and_clumps
[0] = and_clumps
[1];
356 del_slist(&and_clumps
[1]);
359 void __merge_and_clump()
361 struct smatch_state
*tmp
;
363 FOR_EACH_PTR(and_clumps
[0], tmp
) {
364 if (tmp
->state
!= get_state_slist(and_clumps
[1], tmp
->name
,
365 tmp
->owner
, tmp
->sym
))
366 DELETE_CURRENT_PTR(tmp
);
367 } END_FOR_EACH_PTR(tmp
);
368 del_slist(&and_clumps
[1]);
371 void __use_and_clumps()
373 struct smatch_state
*tmp
;
376 FOR_EACH_PTR(and_clumps
[0], tmp
) {
378 set_state_stack(&true_stack
, tmp
->name
, tmp
->owner
,
379 tmp
->sym
, tmp
->state
);
380 } END_FOR_EACH_PTR(tmp
);
381 del_slist(&and_clumps
[0]);
384 void __split_false_states_mini()
386 push_slist(&mini_false_stack
, clone_slist(cur_slist
));
389 void __use_false_states_mini()
391 struct state_list
*slist
;
394 slist
= pop_slist(&mini_false_stack
);
399 void __pop_false_states_mini()
401 struct state_list
*slist
;
403 slist
= pop_slist(&mini_false_stack
);
407 void __split_true_false_paths()
409 push_slist(&false_stack
, clone_slist(cur_slist
));
410 push_slist(&true_stack
, clone_slist(cur_slist
));
411 __split_false_states_mini();
414 void __use_true_states()
416 struct state_list
*slist
;
418 __pop_false_states_mini();
420 slist
= pop_slist(&true_stack
);
425 void __use_false_states()
427 struct state_list
*slist
;
429 push_slist(&true_stack
, clone_slist(cur_slist
));
431 slist
= pop_slist(&false_stack
);
436 void __pop_false_states()
438 struct state_list
*slist
;
440 slist
= pop_slist(&false_stack
);
444 void __merge_false_states()
446 struct state_list
*slist
;
448 slist
= pop_slist(&false_stack
);
453 void __merge_true_states()
455 struct state_list
*slist
;
457 slist
= pop_slist(&true_stack
);
462 void __pop_true_states()
464 struct state_list
*slist
;
466 slist
= pop_slist(&true_stack
);
470 void __push_continues()
472 push_slist(&continue_stack
, NULL
);
475 void __pop_continues()
477 struct state_list
*slist
;
479 slist
= pop_slist(&continue_stack
);
483 void __process_continues()
485 struct smatch_state
*state
;
487 FOR_EACH_PTR(cur_slist
, state
) {
488 merge_state_stack(&continue_stack
, state
->name
, state
->owner
,
489 state
->sym
, state
->state
);
490 } END_FOR_EACH_PTR(state
);
493 void __merge_continues()
495 struct state_list
*slist
;
497 slist
= pop_slist(&continue_stack
);
504 push_slist(&break_stack
, NULL
);
507 void __process_breaks()
509 struct smatch_state
*state
;
511 FOR_EACH_PTR(cur_slist
, state
) {
512 merge_state_stack(&break_stack
, state
->name
, state
->owner
,
513 state
->sym
, state
->state
);
514 } END_FOR_EACH_PTR(state
);
517 void __merge_breaks()
519 struct state_list
*slist
;
521 slist
= pop_slist(&break_stack
);
528 struct state_list
*slist
;
530 slist
= pop_slist(&break_stack
);
534 void __save_switch_states()
536 push_slist(&switch_stack
, clone_slist(cur_slist
));
539 void __merge_switches()
541 struct state_list
*slist
;
543 slist
= pop_slist(&switch_stack
);
545 push_slist(&switch_stack
, slist
);
548 void __pop_switches()
550 struct state_list
*slist
;
552 slist
= pop_slist(&switch_stack
);
556 void __push_default()
558 push_slist(&default_stack
, NULL
);
559 set_state_stack(&default_stack
, "has_default", 0, NULL
, 0);
564 set_state_stack(&default_stack
, "has_default", 0, NULL
, 1);
569 struct state_list
*slist
;
570 struct smatch_state
*state
;
573 slist
= pop_slist(&default_stack
);
574 FOR_EACH_PTR(slist
, state
) {
575 if (!strcmp(state
->name
, "has_default"))
577 } END_FOR_EACH_PTR(state
);
582 static struct slist_head
*alloc_slist_head(const char *name
,
583 struct state_list
*slist
)
585 struct slist_head
*slist_head
= __alloc_slist_head(0);
587 slist_head
->name
= (char *)name
;
588 slist_head
->slist
= slist
;
592 static struct state_list
*get_slist_from_slist_stack(const char *name
)
594 struct slist_head
*tmp
;
596 FOR_EACH_PTR(goto_stack
, tmp
) {
597 if (!strcmp(tmp
->name
, name
))
599 } END_FOR_EACH_PTR(tmp
);
603 void __save_gotos(const char *name
)
605 struct state_list
*slist
;
607 slist
= get_slist_from_slist_stack(name
);
609 struct smatch_state
*state
;
610 FOR_EACH_PTR(cur_slist
, state
) {
611 merge_state_slist(&slist
, state
->name
, state
->owner
,
612 state
->sym
, state
->state
);
613 } END_FOR_EACH_PTR(state
);
616 struct state_list
*slist
;
617 struct slist_head
*slist_head
;
618 slist
= clone_slist(cur_slist
);
619 slist_head
= alloc_slist_head(name
, slist
);
620 add_ptr_list(&goto_stack
, slist_head
);
624 void __merge_gotos(const char *name
)
626 struct state_list
*slist
;
628 slist
= get_slist_from_slist_stack(name
);