2 * sparse/smatch_slist.c
4 * Copyright (C) 2008 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 add_history(struct sm_state
*state
)
23 struct state_history
*tmp
;
27 tmp
= malloc(sizeof(*tmp
));
28 tmp
->loc
= get_lineno();
29 add_ptr_list(&state
->line_history
, tmp
);
32 struct sm_state
*alloc_state(const char *name
, int owner
,
33 struct symbol
*sym
, struct smatch_state
*state
)
35 struct sm_state
*sm_state
= __alloc_sm_state(0);
37 sm_state
->name
= (char *)name
;
38 sm_state
->owner
= owner
;
40 sm_state
->state
= state
;
41 sm_state
->line_history
= NULL
;
42 add_history(sm_state
);
43 sm_state
->pools
= NULL
;
47 struct sm_state
*clone_state(struct sm_state
*s
)
49 return alloc_state(s
->name
, s
->owner
, s
->sym
, s
->state
);
52 /* NULL states go at the end to simplify merge_slist */
53 static int cmp_sm_states(const void *_a
, const void *_b
)
55 const struct sm_state
*a
= _a
;
56 const struct sm_state
*b
= _b
;
66 if (a
->owner
> b
->owner
)
68 if (a
->owner
< b
->owner
)
71 ret
= strcmp(a
->name
, b
->name
);
75 if (!b
->sym
&& a
->sym
)
77 if (!a
->sym
&& b
->sym
)
88 static void check_order(struct state_list
*slist
)
90 struct sm_state
*state
;
91 struct sm_state
*last
= NULL
;
94 FOR_EACH_PTR(slist
, state
) {
95 if (last
&& cmp_sm_states(state
, last
) <= 0) {
96 printf("Error. Unsorted slist %d vs %d, %p vs %p, "
97 "%s vs %s\n", last
->owner
, state
->owner
,
98 last
->sym
, state
->sym
, last
->name
, state
->name
);
102 } END_FOR_EACH_PTR(state
);
109 struct state_list
*clone_slist(struct state_list
*from_slist
)
111 struct sm_state
*state
;
112 struct sm_state
*tmp
;
113 struct state_list
*to_slist
= NULL
;
115 FOR_EACH_PTR(from_slist
, state
) {
116 tmp
= clone_state(state
);
117 add_ptr_list(&to_slist
, tmp
);
118 } END_FOR_EACH_PTR(state
);
120 check_order(to_slist
);
125 // FIXME... shouldn't we free some of these state pointers?
126 struct smatch_state
*merge_states(const char *name
, int owner
,
128 struct smatch_state
*state1
,
129 struct smatch_state
*state2
)
131 struct smatch_state
*ret
;
133 if (state1
== state2
)
135 else if (__has_merge_function(owner
))
136 ret
= __client_merge_function(owner
, name
, sym
, state1
, state2
);
140 SM_DEBUG("%d merge name='%s' owner=%d: %s + %s => %s\n",
141 get_lineno(), name
, owner
, show_state(state1
),
142 show_state(state2
), show_state(ret
));
147 struct smatch_state
*get_state_slist(struct state_list
*slist
, const char *name
, int owner
,
150 struct sm_state
*state
;
155 FOR_EACH_PTR(slist
, state
) {
156 if (state
->owner
== owner
&& state
->sym
== sym
157 && !strcmp(state
->name
, name
))
159 } END_FOR_EACH_PTR(state
);
163 struct sm_state
*get_sm_state_slist(struct state_list
*slist
, const char *name
, int owner
,
166 struct sm_state
*state
;
171 FOR_EACH_PTR(slist
, state
) {
172 if (state
->owner
== owner
&& state
->sym
== sym
173 && !strcmp(state
->name
, name
))
175 } END_FOR_EACH_PTR(state
);
179 void set_state_slist(struct state_list
**slist
, const char *name
, int owner
,
180 struct symbol
*sym
, struct smatch_state
*state
)
182 struct sm_state
*tmp
;
183 struct sm_state
*new = alloc_state(name
, owner
, sym
, state
);
185 FOR_EACH_PTR(*slist
, tmp
) {
186 if (cmp_sm_states(tmp
, new) < 0)
188 else if (cmp_sm_states(tmp
, new) == 0) {
189 __free_sm_state(new);
193 INSERT_CURRENT(new, tmp
);
196 } END_FOR_EACH_PTR(tmp
);
197 add_ptr_list(slist
, new);
200 void delete_state_slist(struct state_list
**slist
, const char *name
, int owner
,
203 struct sm_state
*state
;
205 FOR_EACH_PTR(*slist
, state
) {
206 if (state
->owner
== owner
&& state
->sym
== sym
207 && !strcmp(state
->name
, name
)){
208 delete_ptr_list_entry((struct ptr_list
**)slist
,
210 __free_sm_state(state
);
213 } END_FOR_EACH_PTR(state
);
217 void push_slist(struct state_list_stack
**list_stack
, struct state_list
*slist
)
219 add_ptr_list(list_stack
, slist
);
222 struct state_list
*pop_slist(struct state_list_stack
**list_stack
)
224 struct state_list
*slist
;
226 slist
= last_ptr_list((struct ptr_list
*)*list_stack
);
227 delete_ptr_list_last((struct ptr_list
**)list_stack
);
231 void del_slist(struct state_list
**slist
)
233 __free_ptr_list((struct ptr_list
**)slist
);
236 void del_slist_stack(struct state_list_stack
**slist_stack
)
238 struct state_list
*slist
;
240 FOR_EACH_PTR(*slist_stack
, slist
) {
241 __free_ptr_list((struct ptr_list
**)&slist
);
242 } END_FOR_EACH_PTR(slist
);
243 __free_ptr_list((struct ptr_list
**)slist_stack
);
247 * set_state_stack() sets the state for the top slist on the stack.
249 void set_state_stack(struct state_list_stack
**stack
, const char *name
,
250 int owner
, struct symbol
*sym
, struct smatch_state
*state
)
252 struct state_list
*slist
;
254 slist
= pop_slist(stack
);
255 set_state_slist(&slist
, name
, owner
, sym
, state
);
256 push_slist(stack
, slist
);
260 * get_state_stack() gets the state for the top slist on the stack.
262 struct smatch_state
*get_state_stack(struct state_list_stack
*stack
,
263 const char *name
, int owner
,
266 struct state_list
*slist
;
267 struct smatch_state
*ret
;
269 slist
= pop_slist(&stack
);
270 ret
= get_state_slist(slist
, name
, owner
, sym
);
271 push_slist(&stack
, slist
);
275 static void add_pool(struct sm_state
*state
, struct state_list
**pool
)
277 add_ptr_list(pool
, state
);
278 push_slist(&state
->pools
, *pool
);
281 void merge_slist(struct state_list
**to
, struct state_list
*slist
)
283 struct sm_state
*to_state
, *state
, *tmp
;
284 struct state_list
*results
= NULL
;
285 struct smatch_state
*s
;
286 struct state_list
*implied_to
= NULL
;
287 struct state_list
*implied_from
= NULL
;
294 /* merging a null and nonnull path gives you only the nonnull path */
299 *to
= clone_slist(slist
);
303 PREPARE_PTR_LIST(*to
, to_state
);
304 PREPARE_PTR_LIST(slist
, state
);
306 if (!to_state
&& !state
)
308 if (cmp_sm_states(to_state
, state
) < 0) {
309 s
= merge_states(to_state
->name
, to_state
->owner
,
310 to_state
->sym
, to_state
->state
, NULL
);
311 tmp
= alloc_state(to_state
->name
, to_state
->owner
,
313 add_ptr_list(&results
, tmp
);
314 add_pool(to_state
, &implied_to
);
315 NEXT_PTR_LIST(to_state
);
316 } else if (cmp_sm_states(to_state
, state
) == 0) {
317 if (to_state
->state
== state
->state
) {
320 s
= merge_states(to_state
->name
,
322 to_state
->sym
, to_state
->state
,
324 add_pool(to_state
, &implied_to
);
325 add_pool(state
, &implied_from
);
327 tmp
= alloc_state(to_state
->name
, to_state
->owner
,
329 add_ptr_list(&results
, tmp
);
330 NEXT_PTR_LIST(to_state
);
331 NEXT_PTR_LIST(state
);
333 s
= merge_states(state
->name
, state
->owner
,
334 state
->sym
, state
->state
, NULL
);
335 tmp
= alloc_state(state
->name
, state
->owner
,
337 add_ptr_list(&results
, tmp
);
338 add_pool(state
, &implied_from
);
339 NEXT_PTR_LIST(state
);
342 FINISH_PTR_LIST(state
);
343 FINISH_PTR_LIST(to_state
);
349 push_slist(&implied_pools
, implied_from
);
351 push_slist(&implied_pools
, implied_to
);
354 void filter(struct state_list
**slist
, struct state_list
*filter
)
356 struct sm_state
*s_one
, *s_two
;
357 struct state_list
**results
;
364 results
= malloc(sizeof(*results
));
367 PREPARE_PTR_LIST(*slist
, s_one
);
368 PREPARE_PTR_LIST(filter
, s_two
);
370 if (!s_one
|| !s_two
)
372 if (cmp_sm_states(s_one
, s_two
) < 0) {
373 SM_DEBUG("different missing in new %s\n", s_one
->name
);
374 NEXT_PTR_LIST(s_one
);
375 } else if (cmp_sm_states(s_one
, s_two
) == 0) {
376 if (s_one
->state
== s_two
->state
) {
377 add_ptr_list(results
, s_one
);
378 SM_DEBUG("same %s\n", s_one
->name
);
380 SM_DEBUG("different %s %s vs %s\n", s_one
->name
,
381 show_state(s_one
->state
),
382 show_state(s_two
->state
));
383 NEXT_PTR_LIST(s_one
);
384 NEXT_PTR_LIST(s_two
);
386 SM_DEBUG("different missing in old%s\n", s_two
->name
);
387 NEXT_PTR_LIST(s_two
);
390 FINISH_PTR_LIST(s_two
);
391 FINISH_PTR_LIST(s_one
);
398 * This function is basically the same as popping the top two slists,
399 * overwriting the one with the other and pushing it back on the stack.
400 * The difference is that it checks to see that a mutually exclusive
401 * state isn't included in both stacks.
404 void and_slist_stack(struct state_list_stack
**slist_stack
)
406 struct sm_state
*tmp
;
407 struct smatch_state
*tmp_state
;
408 struct state_list
*tmp_slist
= pop_slist(slist_stack
);
410 FOR_EACH_PTR(tmp_slist
, tmp
) {
411 tmp_state
= get_state_stack(*slist_stack
, tmp
->name
,
412 tmp
->owner
, tmp
->sym
);
413 if (tmp_state
&& tmp_state
!= tmp
->state
) {
414 smatch_msg("mutually exclusive 'and' conditions states "
416 tmp
->name
, show_state(tmp_state
),
417 show_state(tmp
->state
));
418 tmp
->state
= merge_states(tmp
->name
, tmp
->owner
,
419 tmp
->sym
, tmp
->state
,
422 set_state_stack(slist_stack
, tmp
->name
, tmp
->owner
, tmp
->sym
,
425 } END_FOR_EACH_PTR(tmp
);
426 del_slist(&tmp_slist
);
429 void or_slist_stack(struct state_list_stack
**slist_stack
)
431 struct state_list
*one
;
432 struct state_list
*two
;
433 struct state_list
*res
= NULL
;
434 struct sm_state
*tmp
;
435 struct smatch_state
*s
;
437 one
= pop_slist(slist_stack
);
438 two
= pop_slist(slist_stack
);
440 FOR_EACH_PTR(one
, tmp
) {
441 s
= get_state_slist(two
, tmp
->name
, tmp
->owner
, tmp
->sym
);
442 s
= merge_states(tmp
->name
, tmp
->owner
, tmp
->sym
,
444 set_state_slist(&res
, tmp
->name
, tmp
->owner
, tmp
->sym
, s
);
445 } END_FOR_EACH_PTR(tmp
);
448 FOR_EACH_PTR(two
, tmp
) {
449 s
= get_state_slist(one
, tmp
->name
, tmp
->owner
, tmp
->sym
);
450 s
= merge_states(tmp
->name
, tmp
->owner
, tmp
->sym
,
452 set_state_slist(&res
, tmp
->name
, tmp
->owner
, tmp
->sym
, s
);
453 } END_FOR_EACH_PTR(tmp
);
455 push_slist(slist_stack
, res
);
461 struct state_list
**get_slist_from_slist_stack(struct slist_stack
*stack
,
464 struct named_slist
*tmp
;
466 FOR_EACH_PTR(stack
, tmp
) {
467 if (!strcmp(tmp
->name
, name
))
469 } END_FOR_EACH_PTR(tmp
);
473 void overwrite_slist(struct state_list
*from
, struct state_list
**to
)
475 struct sm_state
*tmp
;
477 FOR_EACH_PTR(from
, tmp
) {
478 set_state_slist(to
, tmp
->name
, tmp
->owner
, tmp
->sym
, tmp
->state
);
479 } END_FOR_EACH_PTR(tmp
);