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
;
37 #define SM_DEBUG(msg...) do { if (debug_states) printf(msg); } while (0)
39 void __print_cur_slist()
41 struct smatch_state
*state
;
43 printf("dumping slist at %d\n", get_lineno());
44 FOR_EACH_PTR(cur_slist
, state
) {
45 printf("%s=%d\n", state
->name
, state
->state
);
46 } END_FOR_EACH_PTR(state
);
50 static void add_history(struct smatch_state
*state
)
52 struct state_history
*tmp
;
56 tmp
= malloc(sizeof(*tmp
));
57 tmp
->loc
= get_lineno();
58 add_ptr_list(&state
->line_history
, tmp
);
59 tmp
= malloc(sizeof(*tmp
));
60 tmp
->loc
= get_path_id();
61 add_ptr_list(&state
->line_history
, tmp
);
64 struct smatch_state
*alloc_state(const char *name
, int owner
,
65 struct symbol
*sym
, int state
)
67 struct smatch_state
*sm_state
= __alloc_smatch_state(0);
69 sm_state
->name
= (char *)name
;
70 sm_state
->owner
= owner
;
72 sm_state
->state
= state
;
73 sm_state
->line_history
= NULL
;
74 sm_state
->path_history
= NULL
;
75 add_history(sm_state
);
79 static struct smatch_state
*clone_state(struct smatch_state
*s
)
81 return alloc_state(s
->name
, s
->owner
, s
->sym
, s
->state
);
84 static void push_slist(struct state_list_stack
**list_stack
,
85 struct state_list
*slist
)
87 add_ptr_list(list_stack
, slist
);
90 static struct state_list
*pop_slist(struct state_list_stack
**list_stack
)
92 struct state_list
*slist
;
94 slist
= last_ptr_list((struct ptr_list
*)*list_stack
);
95 delete_ptr_list_entry((struct ptr_list
**)list_stack
, slist
, 1);
99 static struct state_list
*clone_slist(struct state_list
*from_slist
)
101 struct smatch_state
*state
;
102 struct smatch_state
*tmp
;
103 struct state_list
*to_slist
= NULL
;
105 FOR_EACH_PTR(from_slist
, state
) {
106 tmp
= clone_state(state
);
107 add_ptr_list(&to_slist
, tmp
);
108 } END_FOR_EACH_PTR(state
);
112 static void del_slist(struct state_list
**slist
)
114 __free_ptr_list((struct ptr_list
**)slist
);
117 static void del_slist_stack(struct state_list_stack
**slist_stack
)
119 struct state_list
*slist
;
121 FOR_EACH_PTR(*slist_stack
, slist
) {
122 __free_ptr_list((struct ptr_list
**)&slist
);
123 } END_FOR_EACH_PTR(slist
);
124 __free_ptr_list((struct ptr_list
**)slist_stack
);
127 static void add_state_slist(struct state_list
**slist
,
128 struct smatch_state
*state
)
130 add_ptr_list(slist
, state
);
133 static void set_state_slist(struct state_list
**slist
, const char *name
,
134 int owner
, struct symbol
*sym
, int state
)
136 struct smatch_state
*tmp
;
138 FOR_EACH_PTR(*slist
, tmp
) {
139 if (tmp
->owner
== owner
&& tmp
->sym
== sym
140 && !strcmp(tmp
->name
, name
)){
144 } END_FOR_EACH_PTR(tmp
);
145 tmp
= alloc_state(name
, owner
, sym
, state
);
146 add_state_slist(slist
, tmp
);
149 static inline void set_state_stack(struct state_list_stack
**stack
,
150 const char *name
, int owner
,
151 struct symbol
*sym
, int state
)
153 struct state_list
*slist
;
155 slist
= pop_slist(stack
);
156 set_state_slist(&slist
, name
, owner
, sym
, state
);
157 push_slist(stack
, slist
);
160 static int merge_states(const char *name
, int owner
, struct symbol
*sym
,
161 int state1
, int state2
)
163 if (__has_merge_function(owner
))
164 return __client_merge_function(owner
, name
, sym
, state1
,
166 if (state1
== state2
)
171 static void merge_state_slist(struct state_list
**slist
, const char *name
,
172 int owner
, struct symbol
*sym
, int state
)
174 struct smatch_state
*tmp
;
177 FOR_EACH_PTR(*slist
, tmp
) {
178 if (tmp
->owner
== owner
&& tmp
->sym
== sym
179 && !strcmp(tmp
->name
, name
)){
180 s
= merge_states(name
, owner
, sym
, tmp
->state
, state
);
181 if (tmp
->state
!= s
) {
183 SM_DEBUG("%d merge name='%s' owner=%d: %d + %d => %d\n",
184 get_lineno(), name
, owner
, tmp
->state
, state
, s
);
189 } END_FOR_EACH_PTR(tmp
);
190 tmp
= alloc_state(name
, owner
, sym
, state
);
191 add_state_slist(slist
, tmp
);
194 static void merge_state_stack(struct state_list_stack
** stack
,
195 const char *name
, int owner
, struct symbol
*sym
,
198 struct state_list
*slist
;
200 slist
= pop_slist(stack
);
201 merge_state_slist(&slist
, name
, owner
, sym
, state
);
202 push_slist(stack
, slist
);
205 static void delete_state_slist(struct state_list
**slist
, const char *name
,
206 int owner
, struct symbol
*sym
)
208 struct smatch_state
*state
;
210 FOR_EACH_PTR(*slist
, state
) {
211 if (state
->owner
== owner
&& state
->sym
== sym
212 && !strcmp(state
->name
, name
)){
213 delete_ptr_list_entry((struct ptr_list
**)slist
,
215 __free_smatch_state(state
);
218 } END_FOR_EACH_PTR(state
);
221 static void merge_slist(struct state_list
*slist
)
223 struct smatch_state
*state
;
224 FOR_EACH_PTR(slist
, state
) {
225 merge_state_slist(&cur_slist
, state
->name
, state
->owner
,
226 state
->sym
, state
->state
);
227 } END_FOR_EACH_PTR(state
);
230 void set_state(const char *name
, int owner
, struct symbol
*sym
, int state
)
232 struct smatch_state
*tmp
;
237 FOR_EACH_PTR(cur_slist
, tmp
) {
238 if (tmp
->owner
== owner
&& tmp
->sym
== sym
239 && !strcmp(tmp
->name
, name
)){
240 SM_DEBUG("%d state change name='%s' owner=%d: %d => %d\n"
241 , get_lineno(), name
, owner
, tmp
->state
, state
);
246 } END_FOR_EACH_PTR(tmp
);
247 SM_DEBUG("%d new state. name='%s' owner=%d: %d\n", get_lineno(), name
,
249 tmp
= alloc_state(name
, owner
, sym
, state
);
250 add_state_slist(&cur_slist
, tmp
);
254 static int get_state_slist(struct state_list
*slist
, const char *name
,
255 int owner
, struct symbol
*sym
)
257 struct smatch_state
*state
;
262 FOR_EACH_PTR(cur_slist
, state
) {
263 if (state
->owner
== owner
&& state
->sym
== sym
264 && !strcmp(state
->name
, name
))
266 } END_FOR_EACH_PTR(state
);
270 int get_state(const char *name
, int owner
, struct symbol
*sym
)
272 return get_state_slist(cur_slist
, name
, owner
, sym
);
275 struct state_list
*get_current_states(int owner
)
277 struct state_list
*slist
;
278 struct smatch_state
*tmp
;
280 FOR_EACH_PTR(cur_slist
, tmp
) {
281 if (tmp
->owner
== owner
) {
282 add_ptr_list(&slist
, tmp
);
284 } END_FOR_EACH_PTR(tmp
);
289 void set_true_false_states(const char *name
, int owner
, struct symbol
*sym
,
290 int true_state
, int false_state
)
292 int merged
= merge_states(name
, owner
, sym
, true_state
, false_state
);
294 /* fixme. history plus don't call get_state() when not needed*/
295 //SM_DEBUG("%d set_true_false %s. Was %d. Now T:%d F:%d\n",
296 // get_lineno(), name, get_state(name, owner, sym), true_state,
299 if (!false_stack
|| !true_stack
|| !mini_false_stack
) {
300 printf("Error: missing true/false stacks\n");
304 int tmp
= true_state
;
306 true_state
= false_state
;
309 set_state(name
, owner
, sym
, true_state
);
310 set_state_stack(&mini_false_stack
, name
, owner
, sym
, false_state
);
311 set_state_slist(&and_clumps
[1], name
, owner
, sym
, true_state
);
312 set_state_stack(&true_stack
, name
, owner
, sym
,
313 (__ors
?merged
:true_state
));
314 set_state_stack(&false_stack
, name
, owner
, sym
,
315 (__ands
?merged
:false_state
));
318 void delete_state(const char *name
, int owner
, struct symbol
*sym
)
320 delete_state_slist(&cur_slist
, name
, owner
, sym
);
325 del_slist(&cur_slist
);
328 void clear_all_states()
330 struct slist_head
*slist_head
;
333 del_slist_stack(&false_stack
);
334 del_slist_stack(&true_stack
);
335 del_slist_stack(&break_stack
);
336 del_slist_stack(&switch_stack
);
337 del_slist_stack(&continue_stack
);
338 del_slist_stack(&mini_false_stack
);
339 del_slist(&and_clumps
[0]);
340 del_slist(&and_clumps
[1]);
342 FOR_EACH_PTR(goto_stack
, slist_head
) {
343 del_slist(&slist_head
->slist
);
344 } END_FOR_EACH_PTR(slist_head
);
345 __free_ptr_list((struct ptr_list
**)&goto_stack
);
348 void __first_and_clump()
350 and_clumps
[0] = and_clumps
[1];
351 and_clumps
[1] = NULL
;
354 void __merge_and_clump()
356 struct smatch_state
*tmp
;
358 FOR_EACH_PTR(and_clumps
[0], tmp
) {
359 if (tmp
->state
!= get_state_slist(and_clumps
[1], tmp
->name
,
360 tmp
->owner
, tmp
->sym
))
361 DELETE_CURRENT_PTR(tmp
);
362 } END_FOR_EACH_PTR(tmp
);
363 del_slist(&and_clumps
[1]);
366 void __use_and_clumps()
368 struct smatch_state
*tmp
;
371 FOR_EACH_PTR(and_clumps
[0], tmp
) {
373 set_state_stack(&true_stack
, tmp
->name
, tmp
->owner
,
374 tmp
->sym
, tmp
->state
);
375 } END_FOR_EACH_PTR(tmp
);
376 del_slist(&and_clumps
[0]);
379 void __split_false_states_mini()
381 push_slist(&mini_false_stack
, clone_slist(cur_slist
));
384 void __use_false_states_mini()
386 struct state_list
*slist
;
389 slist
= pop_slist(&mini_false_stack
);
394 void __pop_false_states_mini()
396 struct state_list
*slist
;
398 slist
= pop_slist(&mini_false_stack
);
402 void __split_true_false_paths()
404 push_slist(&false_stack
, clone_slist(cur_slist
));
405 push_slist(&true_stack
, clone_slist(cur_slist
));
406 __split_false_states_mini();
409 void __use_true_states()
411 struct state_list
*slist
;
413 __pop_false_states_mini();
415 slist
= pop_slist(&true_stack
);
420 void __use_false_states()
422 struct state_list
*slist
;
424 push_slist(&true_stack
, clone_slist(cur_slist
));
426 slist
= pop_slist(&false_stack
);
431 void __pop_false_states()
433 struct state_list
*slist
;
435 slist
= pop_slist(&false_stack
);
439 void __merge_false_states()
441 struct state_list
*slist
;
443 slist
= pop_slist(&false_stack
);
448 void __merge_true_states()
450 struct state_list
*slist
;
452 slist
= pop_slist(&true_stack
);
457 void __pop_true_states()
459 struct state_list
*slist
;
461 slist
= pop_slist(&true_stack
);
465 void __push_continues()
467 push_slist(&continue_stack
, NULL
);
470 void __pop_continues()
472 struct state_list
*slist
;
474 slist
= pop_slist(&continue_stack
);
478 void __process_continues()
480 struct smatch_state
*state
;
482 FOR_EACH_PTR(cur_slist
, state
) {
483 merge_state_stack(&continue_stack
, state
->name
, state
->owner
,
484 state
->sym
, state
->state
);
485 } END_FOR_EACH_PTR(state
);
488 void __merge_continues()
490 struct state_list
*slist
;
492 slist
= pop_slist(&continue_stack
);
499 push_slist(&break_stack
, NULL
);
502 void __process_breaks()
504 struct smatch_state
*state
;
506 FOR_EACH_PTR(cur_slist
, state
) {
507 merge_state_stack(&break_stack
, state
->name
, state
->owner
,
508 state
->sym
, state
->state
);
509 } END_FOR_EACH_PTR(state
);
512 void __merge_breaks()
514 struct state_list
*slist
;
516 slist
= pop_slist(&break_stack
);
523 struct state_list
*slist
;
525 slist
= pop_slist(&break_stack
);
529 void __save_switch_states()
531 push_slist(&switch_stack
, clone_slist(cur_slist
));
534 void __merge_switches()
536 struct state_list
*slist
;
538 slist
= pop_slist(&switch_stack
);
540 push_slist(&switch_stack
, slist
);
543 void __pop_switches()
545 struct state_list
*slist
;
547 slist
= pop_slist(&switch_stack
);
551 void __push_default()
553 push_slist(&default_stack
, NULL
);
554 set_state_stack(&default_stack
, "has_default", 0, NULL
, 0);
559 set_state_stack(&default_stack
, "has_default", 0, NULL
, 1);
564 struct state_list
*slist
;
565 struct smatch_state
*state
;
568 slist
= pop_slist(&default_stack
);
569 FOR_EACH_PTR(slist
, state
) {
570 if (!strcmp(state
->name
, "has_default"))
572 } END_FOR_EACH_PTR(state
);
577 static struct slist_head
*alloc_slist_head(const char *name
,
578 struct state_list
*slist
)
580 struct slist_head
*slist_head
= __alloc_slist_head(0);
582 slist_head
->name
= (char *)name
;
583 slist_head
->slist
= slist
;
587 static struct state_list
*get_slist_from_slist_stack(const char *name
)
589 struct slist_head
*tmp
;
591 FOR_EACH_PTR(goto_stack
, tmp
) {
592 if (!strcmp(tmp
->name
, name
))
594 } END_FOR_EACH_PTR(tmp
);
598 void __save_gotos(const char *name
)
600 struct state_list
*slist
;
602 slist
= get_slist_from_slist_stack(name
);
604 struct smatch_state
*state
;
605 FOR_EACH_PTR(cur_slist
, state
) {
606 merge_state_slist(&slist
, state
->name
, state
->owner
,
607 state
->sym
, state
->state
);
608 } END_FOR_EACH_PTR(state
);
611 struct state_list
*slist
;
612 struct slist_head
*slist_head
;
613 slist
= clone_slist(cur_slist
);
614 slist_head
= alloc_slist_head(name
, slist
);
615 add_ptr_list(&goto_stack
, slist_head
);
619 void __merge_gotos(const char *name
)
621 struct state_list
*slist
;
623 slist
= get_slist_from_slist_stack(name
);