2 * sparse/smatch_slist.c
4 * Copyright (C) 2008,2009 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
14 #include "smatch_slist.h"
16 ALLOCATOR(sm_state
, "smatch state");
17 ALLOCATOR(named_slist
, "named slist");
21 void __print_slist(struct state_list
*slist
)
23 struct sm_state
*state
;
25 printf("dumping slist at %d\n", get_lineno());
26 FOR_EACH_PTR(slist
, state
) {
27 printf("%d '%s'=%s\n", state
->owner
, state
->name
,
28 show_state(state
->state
));
29 } END_FOR_EACH_PTR(state
);
33 void add_history(struct sm_state
*state
)
35 struct state_history
*tmp
;
39 tmp
= malloc(sizeof(*tmp
));
40 tmp
->loc
= get_lineno();
41 add_ptr_list(&state
->line_history
, tmp
);
44 static void add_possible(struct sm_state
*sm
, struct sm_state
*new)
48 FOR_EACH_PTR(sm
->possible
, tmp
) {
49 if (tmp
->state
< new->state
) {
51 } else if (tmp
->state
== new->state
) {
54 INSERT_CURRENT(new, tmp
);
57 } END_FOR_EACH_PTR(tmp
);
58 add_ptr_list(&sm
->possible
, new);
61 struct sm_state
*alloc_state(const char *name
, int owner
,
62 struct symbol
*sym
, struct smatch_state
*state
)
64 struct sm_state
*sm_state
= __alloc_sm_state(0);
66 sm_state
->name
= (char *)name
;
67 sm_state
->owner
= owner
;
69 sm_state
->state
= state
;
70 sm_state
->line_history
= NULL
;
71 add_history(sm_state
);
72 sm_state
->pools
= NULL
;
73 sm_state
->possible
= NULL
;
74 add_possible(sm_state
, sm_state
);
78 struct sm_state
*clone_state(struct sm_state
*s
)
82 tmp
= alloc_state(s
->name
, s
->owner
, s
->sym
, s
->state
);
83 tmp
->pools
= clone_stack(s
->pools
);
87 /* NULL states go at the end to simplify merge_slist */
88 static int cmp_sm_states(const struct sm_state
*a
, const struct sm_state
*b
)
99 if (a
->owner
> b
->owner
)
101 if (a
->owner
< b
->owner
)
104 ret
= strcmp(a
->name
, b
->name
);
108 if (!b
->sym
&& a
->sym
)
110 if (!a
->sym
&& b
->sym
)
120 int slist_has_state(struct state_list
*slist
, struct smatch_state
*state
)
122 struct sm_state
*tmp
;
124 FOR_EACH_PTR(slist
, tmp
) {
125 if (tmp
->state
== state
)
127 } END_FOR_EACH_PTR(tmp
);
132 static void check_order(struct state_list
*slist
)
134 struct sm_state
*state
;
135 struct sm_state
*last
= NULL
;
138 FOR_EACH_PTR(slist
, state
) {
139 if (last
&& cmp_sm_states(state
, last
) <= 0) {
140 printf("Error. Unsorted slist %d vs %d, %p vs %p, "
141 "%s vs %s\n", last
->owner
, state
->owner
,
142 last
->sym
, state
->sym
, last
->name
, state
->name
);
146 } END_FOR_EACH_PTR(state
);
153 struct state_list
*clone_slist(struct state_list
*from_slist
)
155 struct sm_state
*state
;
156 struct sm_state
*tmp
;
157 struct state_list
*to_slist
= NULL
;
159 FOR_EACH_PTR(from_slist
, state
) {
160 tmp
= clone_state(state
);
161 add_ptr_list(&to_slist
, tmp
);
162 } END_FOR_EACH_PTR(state
);
164 check_order(to_slist
);
169 struct state_list_stack
*clone_stack(struct state_list_stack
*from_stack
)
171 struct state_list
*slist
;
172 struct state_list_stack
*to_stack
= NULL
;
174 FOR_EACH_PTR(from_stack
, slist
) {
175 push_slist(&to_stack
, slist
);
176 } END_FOR_EACH_PTR(slist
);
180 // FIXME... shouldn't we free some of these state pointers?
181 struct smatch_state
*merge_states(const char *name
, int owner
,
183 struct smatch_state
*state1
,
184 struct smatch_state
*state2
)
186 struct smatch_state
*ret
;
188 if (state1
== state2
)
190 else if (__has_merge_function(owner
))
191 ret
= __client_merge_function(owner
, name
, sym
, state1
, state2
);
195 SM_DEBUG("%d merge name='%s' owner=%d: %s + %s => %s\n",
196 get_lineno(), name
, owner
, show_state(state1
),
197 show_state(state2
), show_state(ret
));
202 struct sm_state
*get_sm_state_slist(struct state_list
*slist
, const char *name
,
203 int owner
, struct symbol
*sym
)
205 struct sm_state
*state
;
210 FOR_EACH_PTR(slist
, state
) {
211 if (state
->owner
== owner
&& state
->sym
== sym
212 && !strcmp(state
->name
, name
))
214 } END_FOR_EACH_PTR(state
);
218 struct smatch_state
*get_state_slist(struct state_list
*slist
,
219 const char *name
, int owner
,
222 struct sm_state
*state
;
224 state
= get_sm_state_slist(slist
, name
, owner
, sym
);
230 static void overwrite_sm_state(struct state_list
**slist
,
231 struct sm_state
*state
)
233 struct sm_state
*tmp
;
234 struct sm_state
*new = clone_state(state
); //fixme. why?
236 FOR_EACH_PTR(*slist
, tmp
) {
237 if (cmp_sm_states(tmp
, new) < 0)
239 else if (cmp_sm_states(tmp
, new) == 0) {
240 tmp
->state
= new->state
;
241 tmp
->pools
= new->pools
;
242 tmp
->possible
= new->possible
;
243 __free_sm_state(new);
246 INSERT_CURRENT(new, tmp
);
249 } END_FOR_EACH_PTR(tmp
);
250 add_ptr_list(slist
, new);
253 void set_state_slist(struct state_list
**slist
, const char *name
, int owner
,
254 struct symbol
*sym
, struct smatch_state
*state
)
256 struct sm_state
*tmp
;
257 struct sm_state
*new = alloc_state(name
, owner
, sym
, state
);
259 FOR_EACH_PTR(*slist
, tmp
) {
260 if (cmp_sm_states(tmp
, new) < 0)
262 else if (cmp_sm_states(tmp
, new) == 0) {
265 tmp
->possible
= new->possible
;
266 __free_sm_state(new);
269 INSERT_CURRENT(new, tmp
);
272 } END_FOR_EACH_PTR(tmp
);
273 add_ptr_list(slist
, new);
276 void delete_state_slist(struct state_list
**slist
, const char *name
, int owner
,
279 struct sm_state
*state
;
281 FOR_EACH_PTR(*slist
, state
) {
282 if (state
->owner
== owner
&& state
->sym
== sym
283 && !strcmp(state
->name
, name
)){
284 delete_ptr_list_entry((struct ptr_list
**)slist
,
286 __free_sm_state(state
);
289 } END_FOR_EACH_PTR(state
);
293 void push_slist(struct state_list_stack
**list_stack
, struct state_list
*slist
)
295 add_ptr_list(list_stack
, slist
);
298 struct state_list
*pop_slist(struct state_list_stack
**list_stack
)
300 struct state_list
*slist
;
302 slist
= last_ptr_list((struct ptr_list
*)*list_stack
);
303 delete_ptr_list_last((struct ptr_list
**)list_stack
);
307 void del_slist(struct state_list
**slist
)
309 __free_ptr_list((struct ptr_list
**)slist
);
312 void del_slist_stack(struct state_list_stack
**slist_stack
)
314 struct state_list
*slist
;
316 FOR_EACH_PTR(*slist_stack
, slist
) {
317 __free_ptr_list((struct ptr_list
**)&slist
);
318 } END_FOR_EACH_PTR(slist
);
319 __free_ptr_list((struct ptr_list
**)slist_stack
);
323 * set_state_stack() sets the state for the top slist on the stack.
325 void set_state_stack(struct state_list_stack
**stack
, const char *name
,
326 int owner
, struct symbol
*sym
, struct smatch_state
*state
)
328 struct state_list
*slist
;
330 slist
= pop_slist(stack
);
331 set_state_slist(&slist
, name
, owner
, sym
, state
);
332 push_slist(stack
, slist
);
336 * get_state_stack() gets the state for the top slist on the stack.
338 struct smatch_state
*get_state_stack(struct state_list_stack
*stack
,
339 const char *name
, int owner
,
342 struct state_list
*slist
;
343 struct smatch_state
*ret
;
345 slist
= pop_slist(&stack
);
346 ret
= get_state_slist(slist
, name
, owner
, sym
);
347 push_slist(&stack
, slist
);
351 static void add_pool(struct sm_state
*to
, struct state_list
*new)
353 struct state_list
*tmp
;
355 FOR_EACH_PTR(to
->pools
, tmp
) {
358 else if (tmp
== new) {
361 INSERT_CURRENT(new, tmp
);
364 } END_FOR_EACH_PTR(tmp
);
365 add_ptr_list(&to
->pools
, new);
368 static void copy_pools(struct sm_state
*to
, struct sm_state
*sm
)
370 struct state_list
*tmp
;
372 FOR_EACH_PTR(sm
->pools
, tmp
) {
374 } END_FOR_EACH_PTR(tmp
);
377 void merge_slist(struct state_list
**to
, struct state_list
*slist
)
379 struct sm_state
*to_state
, *state
, *tmp
;
380 struct state_list
*results
= NULL
;
381 struct smatch_state
*s
;
382 struct state_list
*implied_to
= NULL
;
383 struct state_list
*implied_from
= NULL
;
390 /* merging a null and nonnull path gives you only the nonnull path */
395 *to
= clone_slist(slist
);
399 PREPARE_PTR_LIST(*to
, to_state
);
400 PREPARE_PTR_LIST(slist
, state
);
402 if (!to_state
&& !state
)
404 if (cmp_sm_states(to_state
, state
) < 0) {
405 s
= merge_states(to_state
->name
, to_state
->owner
,
406 to_state
->sym
, to_state
->state
, NULL
);
407 tmp
= alloc_state(to_state
->name
, to_state
->owner
,
409 copy_pools(tmp
, to_state
);
411 add_ptr_list(&implied_to
, to_state
);
412 add_pool(tmp
, implied_to
);
414 add_ptr_list(&results
, tmp
);
415 NEXT_PTR_LIST(to_state
);
416 } else if (cmp_sm_states(to_state
, state
) == 0) {
417 if (to_state
->state
== state
->state
) {
419 tmp
= alloc_state(to_state
->name
,
422 copy_pools(tmp
, to_state
);
423 copy_pools(tmp
, state
);
426 s
= merge_states(to_state
->name
,
428 to_state
->sym
, to_state
->state
,
431 tmp
= alloc_state(to_state
->name
,
434 copy_pools(tmp
, to_state
);
435 copy_pools(tmp
, state
);
437 add_ptr_list(&implied_to
, to_state
);
438 add_pool(tmp
, implied_to
);
440 add_ptr_list(&implied_from
, state
);
441 add_pool(tmp
, implied_from
);
443 add_ptr_list(&results
, tmp
);
444 NEXT_PTR_LIST(to_state
);
445 NEXT_PTR_LIST(state
);
447 s
= merge_states(state
->name
, state
->owner
,
448 state
->sym
, state
->state
, NULL
);
449 tmp
= alloc_state(state
->name
, state
->owner
,
451 copy_pools(tmp
, state
);
453 add_ptr_list(&implied_from
, state
);
454 add_pool(tmp
, implied_from
);
456 add_ptr_list(&results
, tmp
);
457 NEXT_PTR_LIST(state
);
460 FINISH_PTR_LIST(state
);
461 FINISH_PTR_LIST(to_state
);
467 push_slist(&implied_pools
, implied_from
);
469 push_slist(&implied_pools
, implied_to
);
473 * If you call set_state() then you need to remove
474 * the state from any pools it's in. Just setting ->pools
475 * to NULL isn't enough.
477 void remove_from_pools(struct sm_state
*old
)
479 struct state_list
*slist
;
484 FOR_EACH_PTR(old
->pools
, slist
) {
485 delete_state_slist(&slist
, old
->name
, old
->owner
, old
->sym
);
486 } END_FOR_EACH_PTR(slist
);
491 * filter() is used to find what states are the same across
492 * a series of slists.
493 * It takes a **slist and a *filter.
494 * It removes everything from **slist that isn't in *filter.
495 * The reason you would want to do this is if you want to
496 * know what other states are true if one state is true. (smatch_implied).
499 void filter(struct state_list
**slist
, struct state_list
*filter
)
501 struct sm_state
*s_one
, *s_two
;
502 struct state_list
**results
;
509 results
= malloc(sizeof(*results
));
512 PREPARE_PTR_LIST(*slist
, s_one
);
513 PREPARE_PTR_LIST(filter
, s_two
);
515 if (!s_one
|| !s_two
)
517 if (cmp_sm_states(s_one
, s_two
) < 0) {
518 SM_DEBUG("different missing in new %s\n", s_one
->name
);
519 NEXT_PTR_LIST(s_one
);
520 } else if (cmp_sm_states(s_one
, s_two
) == 0) {
521 if (s_one
->state
== s_two
->state
) {
522 add_ptr_list(results
, s_one
);
523 SM_DEBUG("same %s\n", s_one
->name
);
525 SM_DEBUG("different %s %s vs %s\n", s_one
->name
,
526 show_state(s_one
->state
),
527 show_state(s_two
->state
));
528 NEXT_PTR_LIST(s_one
);
529 NEXT_PTR_LIST(s_two
);
531 SM_DEBUG("different missing in old%s\n", s_two
->name
);
532 NEXT_PTR_LIST(s_two
);
535 FINISH_PTR_LIST(s_two
);
536 FINISH_PTR_LIST(s_one
);
543 * This function is basically the same as popping the top two slists,
544 * overwriting the one with the other and pushing it back on the stack.
545 * The difference is that it checks to see that a mutually exclusive
546 * state isn't included in both stacks.
549 void and_slist_stack(struct state_list_stack
**slist_stack
)
551 struct sm_state
*tmp
;
552 struct smatch_state
*tmp_state
;
553 struct state_list
*tmp_slist
= pop_slist(slist_stack
);
555 FOR_EACH_PTR(tmp_slist
, tmp
) {
556 tmp_state
= get_state_stack(*slist_stack
, tmp
->name
,
557 tmp
->owner
, tmp
->sym
);
558 if (tmp_state
&& tmp_state
!= tmp
->state
) {
559 smatch_msg("mutually exclusive 'and' conditions states "
561 tmp
->name
, show_state(tmp_state
),
562 show_state(tmp
->state
));
563 tmp
->state
= merge_states(tmp
->name
, tmp
->owner
,
564 tmp
->sym
, tmp
->state
,
567 set_state_stack(slist_stack
, tmp
->name
, tmp
->owner
, tmp
->sym
,
570 } END_FOR_EACH_PTR(tmp
);
571 del_slist(&tmp_slist
);
574 void or_slist_stack(struct state_list_stack
**slist_stack
)
576 struct state_list
*one
;
577 struct state_list
*two
;
578 struct state_list
*res
= NULL
;
579 struct sm_state
*tmp
;
580 struct smatch_state
*s
;
582 one
= pop_slist(slist_stack
);
583 two
= pop_slist(slist_stack
);
585 FOR_EACH_PTR(one
, tmp
) {
586 s
= get_state_slist(two
, tmp
->name
, tmp
->owner
, tmp
->sym
);
587 s
= merge_states(tmp
->name
, tmp
->owner
, tmp
->sym
,
589 set_state_slist(&res
, tmp
->name
, tmp
->owner
, tmp
->sym
, s
);
590 } END_FOR_EACH_PTR(tmp
);
593 FOR_EACH_PTR(two
, tmp
) {
594 s
= get_state_slist(one
, tmp
->name
, tmp
->owner
, tmp
->sym
);
595 s
= merge_states(tmp
->name
, tmp
->owner
, tmp
->sym
,
597 set_state_slist(&res
, tmp
->name
, tmp
->owner
, tmp
->sym
, s
);
598 } END_FOR_EACH_PTR(tmp
);
600 push_slist(slist_stack
, res
);
606 struct state_list
**get_slist_from_slist_stack(struct slist_stack
*stack
,
609 struct named_slist
*tmp
;
611 FOR_EACH_PTR(stack
, tmp
) {
612 if (!strcmp(tmp
->name
, name
))
614 } END_FOR_EACH_PTR(tmp
);
618 void overwrite_slist(struct state_list
*from
, struct state_list
**to
)
620 struct sm_state
*tmp
;
622 FOR_EACH_PTR(from
, tmp
) {
623 overwrite_sm_state(to
, tmp
);
624 } END_FOR_EACH_PTR(tmp
);