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 del_slist(&and_clumps
[0]);
356 and_clumps
[0] = and_clumps
[1];
357 and_clumps
[1] = NULL
;
360 void __merge_and_clump()
362 struct smatch_state
*tmp
;
364 FOR_EACH_PTR(and_clumps
[0], tmp
) {
365 if (tmp
->state
!= get_state_slist(and_clumps
[1], tmp
->name
,
366 tmp
->owner
, tmp
->sym
))
367 DELETE_CURRENT_PTR(tmp
);
368 } END_FOR_EACH_PTR(tmp
);
369 del_slist(&and_clumps
[1]);
372 void __use_and_clumps()
374 struct smatch_state
*tmp
;
377 FOR_EACH_PTR(and_clumps
[0], tmp
) {
379 set_state_stack(&true_stack
, tmp
->name
, tmp
->owner
,
380 tmp
->sym
, tmp
->state
);
381 } END_FOR_EACH_PTR(tmp
);
382 del_slist(&and_clumps
[0]);
385 void __split_false_states_mini()
387 push_slist(&mini_false_stack
, clone_slist(cur_slist
));
390 void __use_false_states_mini()
392 struct state_list
*slist
;
395 slist
= pop_slist(&mini_false_stack
);
400 void __pop_false_states_mini()
402 struct state_list
*slist
;
404 slist
= pop_slist(&mini_false_stack
);
408 void __split_true_false_paths()
410 push_slist(&false_stack
, clone_slist(cur_slist
));
411 push_slist(&true_stack
, clone_slist(cur_slist
));
412 __split_false_states_mini();
415 void __use_true_states()
417 struct state_list
*slist
;
419 __pop_false_states_mini();
421 slist
= pop_slist(&true_stack
);
426 void __use_false_states()
428 struct state_list
*slist
;
430 push_slist(&true_stack
, clone_slist(cur_slist
));
432 slist
= pop_slist(&false_stack
);
437 void __pop_false_states()
439 struct state_list
*slist
;
441 slist
= pop_slist(&false_stack
);
445 void __merge_false_states()
447 struct state_list
*slist
;
449 slist
= pop_slist(&false_stack
);
454 void __merge_true_states()
456 struct state_list
*slist
;
458 slist
= pop_slist(&true_stack
);
463 void __pop_true_states()
465 struct state_list
*slist
;
467 slist
= pop_slist(&true_stack
);
471 void __push_continues()
473 push_slist(&continue_stack
, NULL
);
476 void __pop_continues()
478 struct state_list
*slist
;
480 slist
= pop_slist(&continue_stack
);
484 void __process_continues()
486 struct smatch_state
*state
;
488 FOR_EACH_PTR(cur_slist
, state
) {
489 merge_state_stack(&continue_stack
, state
->name
, state
->owner
,
490 state
->sym
, state
->state
);
491 } END_FOR_EACH_PTR(state
);
494 void __merge_continues()
496 struct state_list
*slist
;
498 slist
= pop_slist(&continue_stack
);
505 push_slist(&break_stack
, NULL
);
508 void __process_breaks()
510 struct smatch_state
*state
;
512 FOR_EACH_PTR(cur_slist
, state
) {
513 merge_state_stack(&break_stack
, state
->name
, state
->owner
,
514 state
->sym
, state
->state
);
515 } END_FOR_EACH_PTR(state
);
518 void __merge_breaks()
520 struct state_list
*slist
;
522 slist
= pop_slist(&break_stack
);
529 struct state_list
*slist
;
531 slist
= pop_slist(&break_stack
);
535 void __save_switch_states()
537 push_slist(&switch_stack
, clone_slist(cur_slist
));
540 void __merge_switches()
542 struct state_list
*slist
;
544 slist
= pop_slist(&switch_stack
);
546 push_slist(&switch_stack
, slist
);
549 void __pop_switches()
551 struct state_list
*slist
;
553 slist
= pop_slist(&switch_stack
);
557 void __push_default()
559 push_slist(&default_stack
, NULL
);
560 set_state_stack(&default_stack
, "has_default", 0, NULL
, 0);
565 set_state_stack(&default_stack
, "has_default", 0, NULL
, 1);
570 struct state_list
*slist
;
571 struct smatch_state
*state
;
574 slist
= pop_slist(&default_stack
);
575 FOR_EACH_PTR(slist
, state
) {
576 if (!strcmp(state
->name
, "has_default"))
578 } END_FOR_EACH_PTR(state
);
583 static struct slist_head
*alloc_slist_head(const char *name
,
584 struct state_list
*slist
)
586 struct slist_head
*slist_head
= __alloc_slist_head(0);
588 slist_head
->name
= (char *)name
;
589 slist_head
->slist
= slist
;
593 static struct state_list
*get_slist_from_slist_stack(const char *name
)
595 struct slist_head
*tmp
;
597 FOR_EACH_PTR(goto_stack
, tmp
) {
598 if (!strcmp(tmp
->name
, name
))
600 } END_FOR_EACH_PTR(tmp
);
604 void __save_gotos(const char *name
)
606 struct state_list
*slist
;
608 slist
= get_slist_from_slist_stack(name
);
610 struct smatch_state
*state
;
611 FOR_EACH_PTR(cur_slist
, state
) {
612 merge_state_slist(&slist
, state
->name
, state
->owner
,
613 state
->sym
, state
->state
);
614 } END_FOR_EACH_PTR(state
);
617 struct state_list
*slist
;
618 struct slist_head
*slist_head
;
619 slist
= clone_slist(cur_slist
);
620 slist_head
= alloc_slist_head(name
, slist
);
621 add_ptr_list(&goto_stack
, slist_head
);
625 void __merge_gotos(const char *name
)
627 struct state_list
*slist
;
629 slist
= get_slist_from_slist_stack(name
);