1 /* Classes for representing the state of interest at a given path of analysis.
2 Copyright (C) 2019-2023 Free Software Foundation, Inc.
3 Contributed by David Malcolm <dmalcolm@redhat.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful, but
13 WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
22 #define INCLUDE_MEMORY
24 #include "coretypes.h"
26 #include "diagnostic-core.h"
27 #include "diagnostic.h"
28 #include "analyzer/analyzer.h"
29 #include "analyzer/analyzer-logging.h"
30 #include "analyzer/sm.h"
33 #include "ordered-hash-map.h"
35 #include "analyzer/call-string.h"
36 #include "analyzer/program-point.h"
37 #include "analyzer/store.h"
38 #include "analyzer/region-model.h"
39 #include "analyzer/program-state.h"
40 #include "analyzer/constraint-manager.h"
41 #include "diagnostic-event-id.h"
42 #include "analyzer/pending-diagnostic.h"
43 #include "analyzer/diagnostic-manager.h"
45 #include "basic-block.h"
47 #include "gimple-iterator.h"
50 #include "analyzer/supergraph.h"
51 #include "analyzer/program-state.h"
52 #include "analyzer/exploded-graph.h"
53 #include "analyzer/state-purge.h"
54 #include "analyzer/call-summary.h"
55 #include "analyzer/analyzer-selftests.h"
61 /* class extrinsic_state. */
63 /* Dump a multiline representation of this state to PP. */
66 extrinsic_state::dump_to_pp (pretty_printer
*pp
) const
68 pp_printf (pp
, "extrinsic_state: %i checker(s)\n", get_num_checkers ());
70 state_machine
*checker
;
71 FOR_EACH_VEC_ELT (m_checkers
, i
, checker
)
73 pp_printf (pp
, "m_checkers[%i]: %qs\n", i
, checker
->get_name ());
74 checker
->dump_to_pp (pp
);
78 /* Dump a multiline representation of this state to OUTF. */
81 extrinsic_state::dump_to_file (FILE *outf
) const
85 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
86 pp
.buffer
->stream
= outf
;
91 /* Dump a multiline representation of this state to stderr. */
94 extrinsic_state::dump () const
96 dump_to_file (stderr
);
99 /* Return a new json::object of the form
100 {"checkers" : array of objects, one for each state_machine}. */
103 extrinsic_state::to_json () const
105 json::object
*ext_state_obj
= new json::object ();
108 json::array
*checkers_arr
= new json::array ();
111 FOR_EACH_VEC_ELT (m_checkers
, i
, sm
)
112 checkers_arr
->append (sm
->to_json ());
113 ext_state_obj
->set ("checkers", checkers_arr
);
116 return ext_state_obj
;
119 /* Get the region_model_manager for this extrinsic_state. */
121 region_model_manager
*
122 extrinsic_state::get_model_manager () const
125 return m_engine
->get_model_manager ();
127 return NULL
; /* for selftests. */
130 /* Try to find a state machine named NAME.
131 If found, return true and write its index to *OUT.
132 Otherwise return false. */
135 extrinsic_state::get_sm_idx_by_name (const char *name
, unsigned *out
) const
139 FOR_EACH_VEC_ELT (m_checkers
, i
, sm
)
140 if (0 == strcmp (name
, sm
->get_name ()))
147 /* NAME not found. */
151 /* struct sm_state_map::entry_t. */
154 sm_state_map::entry_t::cmp (const entry_t
&entry_a
, const entry_t
&entry_b
)
156 gcc_assert (entry_a
.m_state
);
157 gcc_assert (entry_b
.m_state
);
158 if (int cmp_state
= ((int)entry_a
.m_state
->get_id ()
159 - (int)entry_b
.m_state
->get_id ()))
161 if (entry_a
.m_origin
&& entry_b
.m_origin
)
162 return svalue::cmp_ptr (entry_a
.m_origin
, entry_b
.m_origin
);
163 if (entry_a
.m_origin
)
165 if (entry_b
.m_origin
)
170 /* class sm_state_map. */
172 /* sm_state_map's ctor. */
174 sm_state_map::sm_state_map (const state_machine
&sm
)
175 : m_sm (sm
), m_map (), m_global_state (sm
.get_start_state ())
179 /* Clone the sm_state_map. */
182 sm_state_map::clone () const
184 return new sm_state_map (*this);
187 /* Print this sm_state_map to PP.
188 If MODEL is non-NULL, print representative tree values where
192 sm_state_map::print (const region_model
*model
,
193 bool simple
, bool multiline
,
194 pretty_printer
*pp
) const
199 if (m_global_state
!= m_sm
.get_start_state ())
203 pp_string (pp
, "global: ");
204 m_global_state
->dump_to_pp (pp
);
209 auto_vec
<const svalue
*> keys (m_map
.elements ());
210 for (map_t::iterator iter
= m_map
.begin ();
211 iter
!= m_map
.end ();
213 keys
.quick_push ((*iter
).first
);
214 keys
.qsort (svalue::cmp_ptr_ptr
);
217 FOR_EACH_VEC_ELT (keys
, i
, sval
)
222 pp_string (pp
, ", ");
224 if (!flag_dump_noaddr
)
226 pp_pointer (pp
, sval
);
227 pp_string (pp
, ": ");
229 sval
->dump_to_pp (pp
, simple
);
231 entry_t e
= *const_cast <map_t
&> (m_map
).get (sval
);
232 pp_string (pp
, ": ");
233 e
.m_state
->dump_to_pp (pp
);
235 if (tree rep
= model
->get_representative_tree (sval
))
237 pp_string (pp
, " (");
238 dump_quoted_tree (pp
, rep
);
239 pp_character (pp
, ')');
243 pp_string (pp
, " (origin: ");
244 if (!flag_dump_noaddr
)
246 pp_pointer (pp
, e
.m_origin
);
247 pp_string (pp
, ": ");
249 e
.m_origin
->dump_to_pp (pp
, simple
);
251 if (tree rep
= model
->get_representative_tree (e
.m_origin
))
253 pp_string (pp
, " (");
254 dump_quoted_tree (pp
, rep
);
255 pp_character (pp
, ')');
266 /* Dump this object to stderr. */
269 sm_state_map::dump (bool simple
) const
272 pp_format_decoder (&pp
) = default_tree_printer
;
273 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
274 pp
.buffer
->stream
= stderr
;
275 print (NULL
, simple
, true, &pp
);
280 /* Return a new json::object of the form
281 {"global" : (optional) value for global state,
282 SVAL_DESC : value for state}. */
285 sm_state_map::to_json () const
287 json::object
*map_obj
= new json::object ();
289 if (m_global_state
!= m_sm
.get_start_state ())
290 map_obj
->set ("global", m_global_state
->to_json ());
291 for (map_t::iterator iter
= m_map
.begin ();
292 iter
!= m_map
.end ();
295 const svalue
*sval
= (*iter
).first
;
296 entry_t e
= (*iter
).second
;
298 label_text sval_desc
= sval
->get_desc ();
299 map_obj
->set (sval_desc
.get (), e
.m_state
->to_json ());
301 /* This doesn't yet JSONify e.m_origin. */
306 /* Return true if no states have been set within this map
307 (all expressions are for the start state). */
310 sm_state_map::is_empty_p () const
312 return m_map
.elements () == 0 && m_global_state
== m_sm
.get_start_state ();
315 /* Generate a hash value for this sm_state_map. */
318 sm_state_map::hash () const
320 hashval_t result
= 0;
322 /* Accumulate the result by xoring a hash for each slot, so that the
323 result doesn't depend on the ordering of the slots in the map. */
325 for (map_t::iterator iter
= m_map
.begin ();
326 iter
!= m_map
.end ();
329 inchash::hash hstate
;
330 hstate
.add_ptr ((*iter
).first
);
331 entry_t e
= (*iter
).second
;
332 hstate
.add_int (e
.m_state
->get_id ());
333 hstate
.add_ptr (e
.m_origin
);
334 result
^= hstate
.end ();
336 result
^= m_global_state
->get_id ();
341 /* Equality operator for sm_state_map. */
344 sm_state_map::operator== (const sm_state_map
&other
) const
346 if (m_global_state
!= other
.m_global_state
)
349 if (m_map
.elements () != other
.m_map
.elements ())
352 for (map_t::iterator iter
= m_map
.begin ();
353 iter
!= m_map
.end ();
356 const svalue
*sval
= (*iter
).first
;
357 entry_t e
= (*iter
).second
;
358 entry_t
*other_slot
= const_cast <map_t
&> (other
.m_map
).get (sval
);
359 if (other_slot
== NULL
)
361 if (e
!= *other_slot
)
365 gcc_checking_assert (hash () == other
.hash ());
370 /* Get the state of SVAL within this object.
371 States default to the start state. */
373 state_machine::state_t
374 sm_state_map::get_state (const svalue
*sval
,
375 const extrinsic_state
&ext_state
) const
379 sval
= canonicalize_svalue (sval
, ext_state
);
382 = const_cast <map_t
&> (m_map
).get (sval
))
383 return slot
->m_state
;
385 /* SVAL has no explicit sm-state.
386 If this sm allows for state inheritance, then SVAL might have implicit
387 sm-state inherited via a parent.
388 For example INIT_VAL(foo.field) might inherit taintedness state from
390 if (m_sm
.inherited_state_p ())
391 if (region_model_manager
*mgr
= ext_state
.get_model_manager ())
393 if (const initial_svalue
*init_sval
= sval
->dyn_cast_initial_svalue ())
395 const region
*reg
= init_sval
->get_region ();
396 /* Try recursing upwards (up to the base region for the
398 if (!reg
->base_region_p ())
399 if (const region
*parent_reg
= reg
->get_parent_region ())
401 const svalue
*parent_init_sval
402 = mgr
->get_or_create_initial_value (parent_reg
);
403 state_machine::state_t parent_state
404 = get_state (parent_init_sval
, ext_state
);
409 else if (const sub_svalue
*sub_sval
= sval
->dyn_cast_sub_svalue ())
411 const svalue
*parent_sval
= sub_sval
->get_parent ();
412 if (state_machine::state_t parent_state
413 = get_state (parent_sval
, ext_state
))
418 if (state_machine::state_t state
419 = m_sm
.alt_get_inherited_state (*this, sval
, ext_state
))
422 return m_sm
.get_default_state (sval
);
425 /* Get the "origin" svalue for any state of SVAL. */
428 sm_state_map::get_origin (const svalue
*sval
,
429 const extrinsic_state
&ext_state
) const
433 sval
= canonicalize_svalue (sval
, ext_state
);
436 = const_cast <map_t
&> (m_map
).get (sval
);
438 return slot
->m_origin
;
443 /* Set the state of SID within MODEL to STATE, recording that
444 the state came from ORIGIN. */
447 sm_state_map::set_state (region_model
*model
,
449 state_machine::state_t state
,
450 const svalue
*origin
,
451 const extrinsic_state
&ext_state
)
456 /* Reject attempts to set state on UNKNOWN/POISONED. */
457 if (!sval
->can_have_associated_state_p ())
460 equiv_class
&ec
= model
->get_constraints ()->get_equiv_class (sval
);
461 if (!set_state (ec
, state
, origin
, ext_state
))
465 /* Set the state of EC to STATE, recording that the state came from
467 Return true if any states of svalue_ids within EC changed. */
470 sm_state_map::set_state (const equiv_class
&ec
,
471 state_machine::state_t state
,
472 const svalue
*origin
,
473 const extrinsic_state
&ext_state
)
475 bool any_changed
= false;
476 for (const svalue
*sval
: ec
.m_vars
)
477 any_changed
|= impl_set_state (sval
, state
, origin
, ext_state
);
481 /* Set state of SVAL to STATE, bypassing equivalence classes.
482 Return true if the state changed. */
485 sm_state_map::impl_set_state (const svalue
*sval
,
486 state_machine::state_t state
,
487 const svalue
*origin
,
488 const extrinsic_state
&ext_state
)
490 sval
= canonicalize_svalue (sval
, ext_state
);
492 if (get_state (sval
, ext_state
) == state
)
495 gcc_assert (sval
->can_have_associated_state_p ());
497 if (m_sm
.inherited_state_p ())
499 if (const compound_svalue
*compound_sval
500 = sval
->dyn_cast_compound_svalue ())
501 for (auto iter
: *compound_sval
)
503 const svalue
*inner_sval
= iter
.second
;
504 if (inner_sval
->can_have_associated_state_p ())
505 impl_set_state (inner_sval
, state
, origin
, ext_state
);
509 /* Special-case state 0 as the default value. */
512 if (m_map
.get (sval
))
517 m_map
.put (sval
, entry_t (state
, origin
));
521 /* Clear any state for SVAL from this state map. */
524 sm_state_map::clear_any_state (const svalue
*sval
)
529 /* Set the "global" state within this state map to STATE. */
532 sm_state_map::set_global_state (state_machine::state_t state
)
534 m_global_state
= state
;
537 /* Get the "global" state within this state map. */
539 state_machine::state_t
540 sm_state_map::get_global_state () const
542 return m_global_state
;
545 /* Purge any state for SVAL.
546 If !SM::can_purge_p, then report the state as leaking,
550 sm_state_map::on_svalue_leak (const svalue
*sval
,
551 impl_region_model_context
*ctxt
)
553 if (state_machine::state_t state
= get_state (sval
, ctxt
->m_ext_state
))
555 if (!m_sm
.can_purge_p (state
))
556 ctxt
->on_state_leak (m_sm
, sval
, state
);
561 /* Purge any state for svalues that aren't live with respect to LIVE_SVALUES
565 sm_state_map::on_liveness_change (const svalue_set
&live_svalues
,
566 const region_model
*model
,
567 impl_region_model_context
*ctxt
)
569 svalue_set svals_to_unset
;
570 uncertainty_t
*uncertainty
= ctxt
->get_uncertainty ();
572 auto_vec
<const svalue
*> leaked_svals (m_map
.elements ());
573 for (map_t::iterator iter
= m_map
.begin ();
574 iter
!= m_map
.end ();
577 const svalue
*iter_sval
= (*iter
).first
;
578 if (!iter_sval
->live_p (&live_svalues
, model
))
580 svals_to_unset
.add (iter_sval
);
581 entry_t e
= (*iter
).second
;
582 if (!m_sm
.can_purge_p (e
.m_state
))
583 leaked_svals
.quick_push (iter_sval
);
586 if (uncertainty
->unknown_sm_state_p (iter_sval
))
587 svals_to_unset
.add (iter_sval
);
590 leaked_svals
.qsort (svalue::cmp_ptr_ptr
);
594 FOR_EACH_VEC_ELT (leaked_svals
, i
, sval
)
596 entry_t e
= *m_map
.get (sval
);
597 ctxt
->on_state_leak (m_sm
, sval
, e
.m_state
);
600 for (svalue_set::iterator iter
= svals_to_unset
.begin ();
601 iter
!= svals_to_unset
.end (); ++iter
)
602 m_map
.remove (*iter
);
605 /* Purge state from SVAL (in response to a call to an unknown function). */
608 sm_state_map::on_unknown_change (const svalue
*sval
,
610 const extrinsic_state
&ext_state
)
612 svalue_set svals_to_unset
;
614 for (map_t::iterator iter
= m_map
.begin ();
615 iter
!= m_map
.end ();
618 const svalue
*key
= (*iter
).first
;
619 entry_t e
= (*iter
).second
;
620 /* We only want to purge state for some states when things
621 are mutable. For example, in sm-malloc.cc, an on-stack ptr
622 doesn't stop being stack-allocated when passed to an unknown fn. */
623 if (!m_sm
.reset_when_passed_to_unknown_fn_p (e
.m_state
, is_mutable
))
626 svals_to_unset
.add (key
);
627 /* If we have INIT_VAL(BASE_REG), then unset any INIT_VAL(REG)
628 for REG within BASE_REG. */
629 if (const initial_svalue
*init_sval
= sval
->dyn_cast_initial_svalue ())
630 if (const initial_svalue
*init_key
= key
->dyn_cast_initial_svalue ())
632 const region
*changed_reg
= init_sval
->get_region ();
633 const region
*changed_key
= init_key
->get_region ();
634 if (changed_key
->get_base_region () == changed_reg
)
635 svals_to_unset
.add (key
);
639 for (svalue_set::iterator iter
= svals_to_unset
.begin ();
640 iter
!= svals_to_unset
.end (); ++iter
)
641 impl_set_state (*iter
, (state_machine::state_t
)0, NULL
, ext_state
);
644 /* Purge state for things involving SVAL.
645 For use when SVAL changes meaning, at the def_stmt on an SSA_NAME. */
648 sm_state_map::purge_state_involving (const svalue
*sval
,
649 const extrinsic_state
&ext_state
)
651 /* Currently svalue::involves_p requires this. */
652 if (!(sval
->get_kind () == SK_INITIAL
653 || sval
->get_kind () == SK_CONJURED
))
656 svalue_set svals_to_unset
;
658 for (map_t::iterator iter
= m_map
.begin ();
659 iter
!= m_map
.end ();
662 const svalue
*key
= (*iter
).first
;
663 entry_t e
= (*iter
).second
;
664 if (!m_sm
.can_purge_p (e
.m_state
))
666 if (key
->involves_p (sval
))
667 svals_to_unset
.add (key
);
670 for (svalue_set::iterator iter
= svals_to_unset
.begin ();
671 iter
!= svals_to_unset
.end (); ++iter
)
672 impl_set_state (*iter
, (state_machine::state_t
)0, NULL
, ext_state
);
675 /* Comparator for imposing an order on sm_state_map instances. */
678 sm_state_map::cmp (const sm_state_map
&smap_a
, const sm_state_map
&smap_b
)
680 if (int cmp_count
= smap_a
.elements () - smap_b
.elements ())
683 auto_vec
<const svalue
*> keys_a (smap_a
.elements ());
684 for (map_t::iterator iter
= smap_a
.begin ();
685 iter
!= smap_a
.end ();
687 keys_a
.quick_push ((*iter
).first
);
688 keys_a
.qsort (svalue::cmp_ptr_ptr
);
690 auto_vec
<const svalue
*> keys_b (smap_b
.elements ());
691 for (map_t::iterator iter
= smap_b
.begin ();
692 iter
!= smap_b
.end ();
694 keys_b
.quick_push ((*iter
).first
);
695 keys_b
.qsort (svalue::cmp_ptr_ptr
);
698 const svalue
*sval_a
;
699 FOR_EACH_VEC_ELT (keys_a
, i
, sval_a
)
701 const svalue
*sval_b
= keys_b
[i
];
702 if (int cmp_sval
= svalue::cmp_ptr (sval_a
, sval_b
))
704 const entry_t
*e_a
= const_cast <map_t
&> (smap_a
.m_map
).get (sval_a
);
705 const entry_t
*e_b
= const_cast <map_t
&> (smap_b
.m_map
).get (sval_b
);
706 if (int cmp_entry
= entry_t::cmp (*e_a
, *e_b
))
713 /* Canonicalize SVAL before getting/setting it within the map.
714 Convert all NULL pointers to (void *) to avoid state explosions
715 involving all of the various (foo *)NULL vs (bar *)NULL. */
718 sm_state_map::canonicalize_svalue (const svalue
*sval
,
719 const extrinsic_state
&ext_state
)
721 region_model_manager
*mgr
= ext_state
.get_model_manager ();
722 if (mgr
&& sval
->get_type () && POINTER_TYPE_P (sval
->get_type ()))
723 if (tree cst
= sval
->maybe_get_constant ())
725 return mgr
->get_or_create_constant_svalue (null_pointer_node
);
730 /* Attempt to merge this state map with OTHER, writing the result
732 Return true if the merger was possible, false otherwise.
734 Normally, only identical state maps can be merged, so that
735 differences between state maps lead to different enodes
737 However some state machines may support merging states to
738 allow for discarding of less important states, and thus avoid
739 blow-up of the exploded graph. */
742 sm_state_map::can_merge_with_p (const sm_state_map
&other
,
743 const state_machine
&sm
,
744 const extrinsic_state
&ext_state
,
745 sm_state_map
**out
) const
747 /* If identical, then they merge trivially, with a copy. */
756 *out
= new sm_state_map (sm
);
758 /* Otherwise, attempt to merge element by element. */
760 /* Try to merge global state. */
761 if (state_machine::state_t merged_global_state
762 = sm
.maybe_get_merged_state (get_global_state (),
763 other
.get_global_state ()))
764 (*out
)->set_global_state (merged_global_state
);
768 /* Try to merge state each svalue's state (for the union
769 of svalues represented by each smap).
770 Ignore the origin information. */
771 hash_set
<const svalue
*> svals
;
772 for (auto kv
: *this)
773 svals
.add (kv
.first
);
774 for (auto kv
: other
)
775 svals
.add (kv
.first
);
776 for (auto sval
: svals
)
778 state_machine::state_t this_state
= get_state (sval
, ext_state
);
779 state_machine::state_t other_state
= other
.get_state (sval
, ext_state
);
780 if (state_machine::state_t merged_state
781 = sm
.maybe_get_merged_state (this_state
, other_state
))
782 (*out
)->impl_set_state (sval
, merged_state
, NULL
, ext_state
);
787 /* Successfully merged all elements. */
791 /* class program_state. */
793 /* program_state's ctor. */
795 program_state::program_state (const extrinsic_state
&ext_state
)
796 : m_region_model (NULL
),
797 m_checker_states (ext_state
.get_num_checkers ()),
800 engine
*eng
= ext_state
.get_engine ();
801 region_model_manager
*mgr
= eng
->get_model_manager ();
802 m_region_model
= new region_model (mgr
);
803 const int num_states
= ext_state
.get_num_checkers ();
804 for (int i
= 0; i
< num_states
; i
++)
806 sm_state_map
*sm
= new sm_state_map (ext_state
.get_sm (i
));
807 m_checker_states
.quick_push (sm
);
811 /* Attempt to to use R to replay SUMMARY into this object.
812 Return true if it is possible. */
815 sm_state_map::replay_call_summary (call_summary_replay
&r
,
816 const sm_state_map
&summary
)
818 for (auto kv
: summary
.m_map
)
820 const svalue
*summary_sval
= kv
.first
;
821 const svalue
*caller_sval
= r
.convert_svalue_from_summary (summary_sval
);
824 if (!caller_sval
->can_have_associated_state_p ())
826 const svalue
*summary_origin
= kv
.second
.m_origin
;
827 const svalue
*caller_origin
829 ? r
.convert_svalue_from_summary (summary_origin
)
831 // caller_origin can be NULL.
832 m_map
.put (caller_sval
, entry_t (kv
.second
.m_state
, caller_origin
));
834 m_global_state
= summary
.m_global_state
;
838 /* program_state's copy ctor. */
840 program_state::program_state (const program_state
&other
)
841 : m_region_model (new region_model (*other
.m_region_model
)),
842 m_checker_states (other
.m_checker_states
.length ()),
847 FOR_EACH_VEC_ELT (other
.m_checker_states
, i
, smap
)
848 m_checker_states
.quick_push (smap
->clone ());
851 /* program_state's assignment operator. */
854 program_state::operator= (const program_state
&other
)
856 delete m_region_model
;
857 m_region_model
= new region_model (*other
.m_region_model
);
861 FOR_EACH_VEC_ELT (m_checker_states
, i
, smap
)
863 m_checker_states
.truncate (0);
864 gcc_assert (m_checker_states
.space (other
.m_checker_states
.length ()));
866 FOR_EACH_VEC_ELT (other
.m_checker_states
, i
, smap
)
867 m_checker_states
.quick_push (smap
->clone ());
869 m_valid
= other
.m_valid
;
874 /* Move constructor for program_state (when building with C++11). */
875 program_state::program_state (program_state
&&other
)
876 : m_region_model (other
.m_region_model
),
877 m_checker_states (other
.m_checker_states
.length ())
879 other
.m_region_model
= NULL
;
883 FOR_EACH_VEC_ELT (other
.m_checker_states
, i
, smap
)
884 m_checker_states
.quick_push (smap
);
885 other
.m_checker_states
.truncate (0);
887 m_valid
= other
.m_valid
;
890 /* program_state's dtor. */
892 program_state::~program_state ()
894 delete m_region_model
;
897 /* Generate a hash value for this program_state. */
900 program_state::hash () const
902 hashval_t result
= m_region_model
->hash ();
906 FOR_EACH_VEC_ELT (m_checker_states
, i
, smap
)
907 result
^= smap
->hash ();
911 /* Equality operator for program_state.
912 All parts of the program_state (region model, checker states) must
913 equal their counterparts in OTHER for the two program_states to be
917 program_state::operator== (const program_state
&other
) const
919 if (!(*m_region_model
== *other
.m_region_model
))
924 FOR_EACH_VEC_ELT (m_checker_states
, i
, smap
)
925 if (!(*smap
== *other
.m_checker_states
[i
]))
928 gcc_checking_assert (hash () == other
.hash ());
933 /* Print a compact representation of this state to PP. */
936 program_state::print (const extrinsic_state
&ext_state
,
937 pretty_printer
*pp
) const
939 pp_printf (pp
, "rmodel: ");
940 m_region_model
->dump_to_pp (pp
, true, false);
945 FOR_EACH_VEC_ELT (m_checker_states
, i
, smap
)
947 if (!smap
->is_empty_p ())
949 pp_printf (pp
, "%s: ", ext_state
.get_name (i
));
950 smap
->print (m_region_model
, true, false, pp
);
956 pp_printf (pp
, "invalid state");
961 /* Dump a representation of this state to PP. */
964 program_state::dump_to_pp (const extrinsic_state
&ext_state
,
965 bool /*summarize*/, bool multiline
,
966 pretty_printer
*pp
) const
971 pp_printf (pp
, "rmodel:");
975 pp_string (pp
, " {");
976 m_region_model
->dump_to_pp (pp
, true, multiline
);
983 FOR_EACH_VEC_ELT (m_checker_states
, i
, smap
)
985 if (!smap
->is_empty_p ())
988 pp_string (pp
, " {");
989 pp_printf (pp
, "%s: ", ext_state
.get_name (i
));
992 smap
->print (m_region_model
, true, multiline
, pp
);
1002 pp_printf (pp
, "invalid state");
1007 pp_string (pp
, "}");
1010 /* Dump a representation of this state to OUTF. */
1013 program_state::dump_to_file (const extrinsic_state
&ext_state
,
1014 bool summarize
, bool multiline
,
1018 pp_format_decoder (&pp
) = default_tree_printer
;
1020 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
1021 pp
.buffer
->stream
= outf
;
1022 dump_to_pp (ext_state
, summarize
, multiline
, &pp
);
1026 /* Dump a multiline representation of this state to stderr. */
1029 program_state::dump (const extrinsic_state
&ext_state
,
1030 bool summarize
) const
1032 dump_to_file (ext_state
, summarize
, true, stderr
);
1035 /* Return a new json::object of the form
1036 {"store" : object for store,
1037 "constraints" : object for constraint_manager,
1038 "curr_frame" : (optional) str for current frame,
1039 "checkers" : { STATE_NAME : object per sm_state_map },
1040 "valid" : true/false}. */
1043 program_state::to_json (const extrinsic_state
&ext_state
) const
1045 json::object
*state_obj
= new json::object ();
1047 state_obj
->set ("store", m_region_model
->get_store ()->to_json ());
1048 state_obj
->set ("constraints",
1049 m_region_model
->get_constraints ()->to_json ());
1050 if (m_region_model
->get_current_frame ())
1051 state_obj
->set ("curr_frame",
1052 m_region_model
->get_current_frame ()->to_json ());
1054 /* Provide m_checker_states as an object, using names as keys. */
1056 json::object
*checkers_obj
= new json::object ();
1060 FOR_EACH_VEC_ELT (m_checker_states
, i
, smap
)
1061 if (!smap
->is_empty_p ())
1062 checkers_obj
->set (ext_state
.get_name (i
), smap
->to_json ());
1064 state_obj
->set ("checkers", checkers_obj
);
1067 state_obj
->set ("valid", new json::literal (m_valid
));
1072 /* Update this program_state to reflect a top-level call to FUN.
1073 The params will have initial_svalues. */
1076 program_state::push_frame (const extrinsic_state
&ext_state ATTRIBUTE_UNUSED
,
1079 m_region_model
->push_frame (fun
, NULL
, NULL
);
1082 /* Get the current function of this state. */
1085 program_state::get_current_function () const
1087 return m_region_model
->get_current_function ();
1090 /* Determine if following edge SUCC from ENODE is valid within the graph EG
1091 and update this state accordingly in-place.
1093 Return true if the edge can be followed, or false otherwise.
1095 Check for relevant conditionals and switch-values for conditionals
1096 and switch statements, adding the relevant conditions to this state.
1097 Push/pop frames for interprocedural edges and update params/returned
1100 This is the "state" half of exploded_node::on_edge. */
1103 program_state::on_edge (exploded_graph
&eg
,
1104 exploded_node
*enode
,
1105 const superedge
*succ
,
1106 uncertainty_t
*uncertainty
)
1108 class my_path_context
: public path_context
1111 my_path_context (bool &terminated
) : m_terminated (terminated
) {}
1112 void bifurcate (std::unique_ptr
<custom_edge_info
>) final override
1117 void terminate_path () final override
1119 m_terminated
= true;
1122 bool terminate_path_p () const final override
1124 return m_terminated
;
1130 const program_point
&point
= enode
->get_point ();
1131 const gimple
*last_stmt
= point
.get_supernode ()->get_last_stmt ();
1133 /* For conditionals and switch statements, add the
1134 relevant conditions (for the specific edge) to new_state;
1135 skip edges for which the resulting constraints
1137 This also updates frame information for call/return superedges.
1138 Adding the relevant conditions for the edge could also trigger
1139 sm-state transitions (e.g. transitions due to ptrs becoming known
1140 to be NULL or non-NULL) */
1141 bool terminated
= false;
1142 my_path_context
path_ctxt (terminated
);
1143 impl_region_model_context
ctxt (eg
, enode
,
1144 &enode
->get_state (),
1146 uncertainty
, &path_ctxt
,
1148 if (!m_region_model
->maybe_update_for_edge (*succ
,
1152 logger
* const logger
= eg
.get_logger ();
1154 logger
->log ("edge to SN: %i is impossible"
1155 " due to region_model constraints",
1156 succ
->m_dest
->m_index
);
1162 program_state::detect_leaks (enode
->get_state (), *this,
1163 NULL
, eg
.get_ext_state (),
1169 /* Update this program_state to reflect a call to function
1170 represented by CALL_STMT.
1171 currently used only when the call doesn't have a superedge representing
1172 the call ( like call via a function pointer ) */
1174 program_state::push_call (exploded_graph
&eg
,
1175 exploded_node
*enode
,
1176 const gcall
*call_stmt
,
1177 uncertainty_t
*uncertainty
)
1180 const program_point
&point
= enode
->get_point ();
1181 const gimple
*last_stmt
= point
.get_supernode ()->get_last_stmt ();
1183 impl_region_model_context
ctxt (eg
, enode
,
1184 &enode
->get_state (),
1189 m_region_model
->update_for_gcall (call_stmt
, &ctxt
);
1192 /* Update this program_state to reflect a return from function
1193 call to which is represented by CALL_STMT.
1194 currently used only when the call doesn't have a superedge representing
1197 program_state::returning_call (exploded_graph
&eg
,
1198 exploded_node
*enode
,
1199 const gcall
*call_stmt
,
1200 uncertainty_t
*uncertainty
)
1203 const program_point
&point
= enode
->get_point ();
1204 const gimple
*last_stmt
= point
.get_supernode ()->get_last_stmt ();
1206 impl_region_model_context
ctxt (eg
, enode
,
1207 &enode
->get_state (),
1212 m_region_model
->update_for_return_gcall (call_stmt
, &ctxt
);
1215 /* Generate a simpler version of THIS, discarding state that's no longer
1217 The idea is that we're more likely to be able to consolidate
1218 multiple (point, state) into single exploded_nodes if we discard
1219 irrelevant state (e.g. at the end of functions). */
1222 program_state::prune_for_point (exploded_graph
&eg
,
1223 const program_point
&point
,
1224 exploded_node
*enode_for_diag
,
1225 uncertainty_t
*uncertainty
) const
1227 logger
* const logger
= eg
.get_logger ();
1230 function
*fun
= point
.get_function ();
1234 program_state
new_state (*this);
1236 const state_purge_map
*pm
= eg
.get_purge_map ();
1239 unsigned num_ssas_purged
= 0;
1240 unsigned num_decls_purged
= 0;
1241 auto_vec
<const decl_region
*> regs
;
1242 new_state
.m_region_model
->get_regions_for_current_frame (®s
);
1243 regs
.qsort (region::cmp_ptr_ptr
);
1245 const decl_region
*reg
;
1246 FOR_EACH_VEC_ELT (regs
, i
, reg
)
1248 const tree node
= reg
->get_decl ();
1249 if (TREE_CODE (node
) == SSA_NAME
)
1251 const tree ssa_name
= node
;
1252 const state_purge_per_ssa_name
&per_ssa
1253 = pm
->get_data_for_ssa_name (node
);
1254 if (!per_ssa
.needed_at_point_p (point
.get_function_point ()))
1256 /* Don't purge bindings of SSA names to svalues
1257 that have unpurgable sm-state, so that leaks are
1258 reported at the end of the function, rather than
1259 at the last place that such an SSA name is referred to.
1261 But do purge them for temporaries (when SSA_NAME_VAR is
1262 NULL), so that we report for cases where a leak happens when
1263 a variable is overwritten with another value, so that the leak
1264 is reported at the point of overwrite, rather than having
1265 temporaries keep the value reachable until the frame is
1268 = new_state
.m_region_model
->get_store_value (reg
, NULL
);
1269 if (!new_state
.can_purge_p (eg
.get_ext_state (), sval
)
1270 && SSA_NAME_VAR (ssa_name
))
1272 /* (currently only state maps can keep things
1275 logger
->log ("not purging binding for %qE"
1276 " (used by state map)", ssa_name
);
1280 new_state
.m_region_model
->purge_region (reg
);
1286 const tree decl
= node
;
1287 gcc_assert (TREE_CODE (node
) == VAR_DECL
1288 || TREE_CODE (node
) == PARM_DECL
1289 || TREE_CODE (node
) == RESULT_DECL
);
1290 if (const state_purge_per_decl
*per_decl
1291 = pm
->get_any_data_for_decl (decl
))
1292 if (!per_decl
->needed_at_point_p (point
.get_function_point ()))
1294 /* Don't purge bindings of decls if there are svalues
1295 that have unpurgable sm-state within the decl's cluster,
1296 so that leaks are reported at the end of the function,
1297 rather than at the last place that such a decl is
1299 if (!new_state
.can_purge_base_region_p (eg
.get_ext_state (),
1302 /* (currently only state maps can keep things
1305 logger
->log ("not purging binding for %qE"
1306 " (value in binding used by state map)",
1311 new_state
.m_region_model
->purge_region (reg
);
1317 if (num_ssas_purged
> 0 || num_decls_purged
> 0)
1321 logger
->log ("num_ssas_purged: %i", num_ssas_purged
);
1322 logger
->log ("num_decl_purged: %i", num_decls_purged
);
1324 impl_region_model_context
ctxt (eg
, enode_for_diag
,
1329 detect_leaks (*this, new_state
, NULL
, eg
.get_ext_state (), &ctxt
);
1333 new_state
.m_region_model
->canonicalize ();
1338 /* Return true if there are no unpurgeable bindings within BASE_REG. */
1341 program_state::can_purge_base_region_p (const extrinsic_state
&ext_state
,
1342 const region
*base_reg
) const
1344 binding_cluster
*cluster
1345 = m_region_model
->get_store ()->get_cluster (base_reg
);
1349 for (auto iter
: *cluster
)
1351 const svalue
*sval
= iter
.second
;
1352 if (!can_purge_p (ext_state
, sval
))
1359 /* Get a representative tree to use for describing SVAL. */
1362 program_state::get_representative_tree (const svalue
*sval
) const
1364 gcc_assert (m_region_model
);
1365 return m_region_model
->get_representative_tree (sval
);
1368 /* Attempt to merge this state with OTHER, both at POINT.
1369 Write the result to *OUT.
1370 If the states were merged successfully, return true. */
1373 program_state::can_merge_with_p (const program_state
&other
,
1374 const extrinsic_state
&ext_state
,
1375 const program_point
&point
,
1376 program_state
*out
) const
1379 gcc_assert (m_region_model
);
1381 /* Attempt to merge the sm-states. */
1384 FOR_EACH_VEC_ELT (out
->m_checker_states
, i
, smap
)
1385 if (!m_checker_states
[i
]->can_merge_with_p (*other
.m_checker_states
[i
],
1386 ext_state
.get_sm (i
),
1388 &out
->m_checker_states
[i
]))
1391 /* Attempt to merge the region_models. */
1392 if (!m_region_model
->can_merge_with_p (*other
.m_region_model
,
1394 out
->m_region_model
,
1399 out
->m_region_model
->canonicalize ();
1404 /* Assert that this object is valid. */
1407 program_state::validate (const extrinsic_state
&ext_state
) const
1409 /* Skip this in a release build. */
1414 gcc_assert (m_checker_states
.length () == ext_state
.get_num_checkers ());
1415 m_region_model
->validate ();
1419 log_set_of_svalues (logger
*logger
, const char *name
,
1420 const svalue_set
&set
)
1423 logger
->inc_indent ();
1424 auto_vec
<const svalue
*> sval_vecs (set
.elements ());
1425 for (svalue_set::iterator iter
= set
.begin ();
1426 iter
!= set
.end (); ++iter
)
1427 sval_vecs
.quick_push (*iter
);
1428 sval_vecs
.qsort (svalue::cmp_ptr_ptr
);
1431 FOR_EACH_VEC_ELT (sval_vecs
, i
, sval
)
1433 logger
->start_log_line ();
1434 pretty_printer
*pp
= logger
->get_printer ();
1435 if (!flag_dump_noaddr
)
1437 pp_pointer (pp
, sval
);
1438 pp_string (pp
, ": ");
1440 sval
->dump_to_pp (pp
, false);
1441 logger
->end_log_line ();
1443 logger
->dec_indent ();
1446 /* Compare the sets of svalues reachable from each of SRC_STATE and DEST_STATE.
1447 For all svalues that are reachable in SRC_STATE and are not live in
1448 DEST_STATE (whether explicitly reachable in DEST_STATE, or implicitly live
1449 based on the former set), call CTXT->on_svalue_leak for them.
1451 Call on_liveness_change on both the CTXT and on the DEST_STATE's
1452 constraint_manager, purging dead svalues from sm-state and from
1453 constraints, respectively.
1455 This function should be called at each fine-grained state change, not
1456 just at exploded edges. */
1459 program_state::detect_leaks (const program_state
&src_state
,
1460 const program_state
&dest_state
,
1461 const svalue
*extra_sval
,
1462 const extrinsic_state
&ext_state
,
1463 region_model_context
*ctxt
)
1465 logger
*logger
= ext_state
.get_logger ();
1467 const uncertainty_t
*uncertainty
= ctxt
->get_uncertainty ();
1470 pretty_printer
*pp
= logger
->get_printer ();
1471 logger
->start_log_line ();
1472 pp_string (pp
, "src_state: ");
1473 src_state
.dump_to_pp (ext_state
, true, false, pp
);
1474 logger
->end_log_line ();
1475 logger
->start_log_line ();
1476 pp_string (pp
, "dest_state: ");
1477 dest_state
.dump_to_pp (ext_state
, true, false, pp
);
1478 logger
->end_log_line ();
1481 logger
->start_log_line ();
1482 pp_string (pp
, "extra_sval: ");
1483 extra_sval
->dump_to_pp (pp
, true);
1484 logger
->end_log_line ();
1488 logger
->start_log_line ();
1489 pp_string (pp
, "uncertainty: ");
1490 uncertainty
->dump_to_pp (pp
, true);
1491 logger
->end_log_line ();
1495 /* Get svalues reachable from each of src_state and dest_state.
1496 Get svalues *known* to be reachable in src_state.
1497 Pass in uncertainty for dest_state so that we additionally get svalues that
1498 *might* still be reachable in dst_state. */
1499 svalue_set known_src_svalues
;
1500 src_state
.m_region_model
->get_reachable_svalues (&known_src_svalues
,
1502 svalue_set maybe_dest_svalues
;
1503 dest_state
.m_region_model
->get_reachable_svalues (&maybe_dest_svalues
,
1504 extra_sval
, uncertainty
);
1508 log_set_of_svalues (logger
, "src_state known reachable svalues:",
1510 log_set_of_svalues (logger
, "dest_state maybe reachable svalues:",
1511 maybe_dest_svalues
);
1514 auto_vec
<const svalue
*> dead_svals (known_src_svalues
.elements ());
1515 for (svalue_set::iterator iter
= known_src_svalues
.begin ();
1516 iter
!= known_src_svalues
.end (); ++iter
)
1518 const svalue
*sval
= (*iter
);
1519 /* For each sval reachable from SRC_STATE, determine if it is
1520 live in DEST_STATE: either explicitly reachable, implicitly
1521 live based on the set of explicitly reachable svalues,
1522 or possibly reachable as recorded in uncertainty.
1523 Record those that have ceased to be live i.e. were known
1524 to be live, and are now not known to be even possibly-live. */
1525 if (!sval
->live_p (&maybe_dest_svalues
, dest_state
.m_region_model
))
1526 dead_svals
.quick_push (sval
);
1529 /* Call CTXT->on_svalue_leak on all svals in SRC_STATE that have ceased
1530 to be live, sorting them first to ensure deterministic behavior. */
1531 dead_svals
.qsort (svalue::cmp_ptr_ptr
);
1534 FOR_EACH_VEC_ELT (dead_svals
, i
, sval
)
1535 ctxt
->on_svalue_leak (sval
);
1537 /* Purge dead svals from sm-state. */
1538 ctxt
->on_liveness_change (maybe_dest_svalues
,
1539 dest_state
.m_region_model
);
1541 /* Purge dead svals from constraints. */
1542 dest_state
.m_region_model
->get_constraints ()->on_liveness_change
1543 (maybe_dest_svalues
, dest_state
.m_region_model
);
1545 /* Purge dead heap-allocated regions from dynamic extents. */
1546 for (const svalue
*sval
: dead_svals
)
1547 if (const region
*reg
= sval
->maybe_get_region ())
1548 if (reg
->get_kind () == RK_HEAP_ALLOCATED
)
1549 dest_state
.m_region_model
->unset_dynamic_extents (reg
);
1552 /* Attempt to to use R to replay SUMMARY into this object.
1553 Return true if it is possible. */
1556 program_state::replay_call_summary (call_summary_replay
&r
,
1557 const program_state
&summary
)
1559 if (!m_region_model
->replay_call_summary (r
, *summary
.m_region_model
))
1562 for (unsigned sm_idx
= 0; sm_idx
< m_checker_states
.length (); sm_idx
++)
1564 const sm_state_map
*summary_sm_map
= summary
.m_checker_states
[sm_idx
];
1565 m_checker_states
[sm_idx
]->replay_call_summary (r
, *summary_sm_map
);
1568 if (!summary
.m_valid
)
1574 /* Handle calls to "__analyzer_dump_state". */
1577 program_state::impl_call_analyzer_dump_state (const gcall
*call
,
1578 const extrinsic_state
&ext_state
,
1579 region_model_context
*ctxt
)
1581 call_details
cd (call
, m_region_model
, ctxt
);
1582 const char *sm_name
= cd
.get_arg_string_literal (0);
1585 error_at (call
->location
, "cannot determine state machine");
1589 if (!ext_state
.get_sm_idx_by_name (sm_name
, &sm_idx
))
1591 error_at (call
->location
, "unrecognized state machine %qs", sm_name
);
1594 const sm_state_map
*smap
= m_checker_states
[sm_idx
];
1596 const svalue
*sval
= cd
.get_arg_svalue (1);
1598 /* Strip off cast to int (due to variadic args). */
1599 if (const svalue
*cast
= sval
->maybe_undo_cast ())
1602 state_machine::state_t state
= smap
->get_state (sval
, ext_state
);
1603 warning_at (call
->location
, 0, "state: %qs", state
->get_name ());
1608 namespace selftest
{
1610 /* Tests for sm_state_map. */
1613 test_sm_state_map ()
1615 tree x
= build_global_decl ("x", integer_type_node
);
1616 tree y
= build_global_decl ("y", integer_type_node
);
1617 tree z
= build_global_decl ("z", integer_type_node
);
1619 state_machine
*sm
= make_malloc_state_machine (NULL
);
1620 auto_delete_vec
<state_machine
> checkers
;
1621 checkers
.safe_push (sm
);
1623 extrinsic_state
ext_state (checkers
, &eng
);
1624 state_machine::state_t start
= sm
->get_start_state ();
1626 /* Test setting states on svalue_id instances directly. */
1628 const state_machine::state
test_state_42 ("test state 42", 42);
1629 const state_machine::state_t TEST_STATE_42
= &test_state_42
;
1630 region_model_manager mgr
;
1631 region_model
model (&mgr
);
1632 const svalue
*x_sval
= model
.get_rvalue (x
, NULL
);
1633 const svalue
*y_sval
= model
.get_rvalue (y
, NULL
);
1634 const svalue
*z_sval
= model
.get_rvalue (z
, NULL
);
1636 sm_state_map
map (*sm
);
1637 ASSERT_TRUE (map
.is_empty_p ());
1638 ASSERT_EQ (map
.get_state (x_sval
, ext_state
), start
);
1640 map
.impl_set_state (x_sval
, TEST_STATE_42
, z_sval
, ext_state
);
1641 ASSERT_EQ (map
.get_state (x_sval
, ext_state
), TEST_STATE_42
);
1642 ASSERT_EQ (map
.get_origin (x_sval
, ext_state
), z_sval
);
1643 ASSERT_EQ (map
.get_state (y_sval
, ext_state
), start
);
1644 ASSERT_FALSE (map
.is_empty_p ());
1646 map
.impl_set_state (y_sval
, 0, z_sval
, ext_state
);
1647 ASSERT_EQ (map
.get_state (y_sval
, ext_state
), start
);
1649 map
.impl_set_state (x_sval
, 0, z_sval
, ext_state
);
1650 ASSERT_EQ (map
.get_state (x_sval
, ext_state
), start
);
1651 ASSERT_TRUE (map
.is_empty_p ());
1654 const state_machine::state
test_state_5 ("test state 5", 5);
1655 const state_machine::state_t TEST_STATE_5
= &test_state_5
;
1657 /* Test setting states via equivalence classes. */
1659 region_model_manager mgr
;
1660 region_model
model (&mgr
);
1661 const svalue
*x_sval
= model
.get_rvalue (x
, NULL
);
1662 const svalue
*y_sval
= model
.get_rvalue (y
, NULL
);
1663 const svalue
*z_sval
= model
.get_rvalue (z
, NULL
);
1665 sm_state_map
map (*sm
);
1666 ASSERT_TRUE (map
.is_empty_p ());
1667 ASSERT_EQ (map
.get_state (x_sval
, ext_state
), start
);
1668 ASSERT_EQ (map
.get_state (y_sval
, ext_state
), start
);
1670 model
.add_constraint (x
, EQ_EXPR
, y
, NULL
);
1672 /* Setting x to a state should also update y, as they
1673 are in the same equivalence class. */
1674 map
.set_state (&model
, x_sval
, TEST_STATE_5
, z_sval
, ext_state
);
1675 ASSERT_EQ (map
.get_state (x_sval
, ext_state
), TEST_STATE_5
);
1676 ASSERT_EQ (map
.get_state (y_sval
, ext_state
), TEST_STATE_5
);
1677 ASSERT_EQ (map
.get_origin (x_sval
, ext_state
), z_sval
);
1678 ASSERT_EQ (map
.get_origin (y_sval
, ext_state
), z_sval
);
1681 /* Test equality and hashing. */
1683 region_model_manager mgr
;
1684 region_model
model (&mgr
);
1685 const svalue
*y_sval
= model
.get_rvalue (y
, NULL
);
1686 const svalue
*z_sval
= model
.get_rvalue (z
, NULL
);
1688 sm_state_map
map0 (*sm
);
1689 sm_state_map
map1 (*sm
);
1690 sm_state_map
map2 (*sm
);
1692 ASSERT_EQ (map0
.hash (), map1
.hash ());
1693 ASSERT_EQ (map0
, map1
);
1695 map1
.impl_set_state (y_sval
, TEST_STATE_5
, z_sval
, ext_state
);
1696 ASSERT_NE (map0
.hash (), map1
.hash ());
1697 ASSERT_NE (map0
, map1
);
1699 /* Make the same change to map2. */
1700 map2
.impl_set_state (y_sval
, TEST_STATE_5
, z_sval
, ext_state
);
1701 ASSERT_EQ (map1
.hash (), map2
.hash ());
1702 ASSERT_EQ (map1
, map2
);
1705 /* Equality and hashing shouldn't depend on ordering. */
1707 const state_machine::state
test_state_2 ("test state 2", 2);
1708 const state_machine::state_t TEST_STATE_2
= &test_state_2
;
1709 const state_machine::state
test_state_3 ("test state 3", 3);
1710 const state_machine::state_t TEST_STATE_3
= &test_state_3
;
1711 sm_state_map
map0 (*sm
);
1712 sm_state_map
map1 (*sm
);
1713 sm_state_map
map2 (*sm
);
1715 ASSERT_EQ (map0
.hash (), map1
.hash ());
1716 ASSERT_EQ (map0
, map1
);
1718 region_model_manager mgr
;
1719 region_model
model (&mgr
);
1720 const svalue
*x_sval
= model
.get_rvalue (x
, NULL
);
1721 const svalue
*y_sval
= model
.get_rvalue (y
, NULL
);
1722 const svalue
*z_sval
= model
.get_rvalue (z
, NULL
);
1724 map1
.impl_set_state (x_sval
, TEST_STATE_2
, NULL
, ext_state
);
1725 map1
.impl_set_state (y_sval
, TEST_STATE_3
, NULL
, ext_state
);
1726 map1
.impl_set_state (z_sval
, TEST_STATE_2
, NULL
, ext_state
);
1728 map2
.impl_set_state (z_sval
, TEST_STATE_2
, NULL
, ext_state
);
1729 map2
.impl_set_state (y_sval
, TEST_STATE_3
, NULL
, ext_state
);
1730 map2
.impl_set_state (x_sval
, TEST_STATE_2
, NULL
, ext_state
);
1732 ASSERT_EQ (map1
.hash (), map2
.hash ());
1733 ASSERT_EQ (map1
, map2
);
1736 // TODO: coverage for purging
1739 /* Check program_state works as expected. */
1742 test_program_state_1 ()
1744 /* Create a program_state for a global ptr "p" that has
1745 malloc sm-state, pointing to a region on the heap. */
1746 tree p
= build_global_decl ("p", ptr_type_node
);
1748 state_machine
*sm
= make_malloc_state_machine (NULL
);
1749 const state_machine::state_t UNCHECKED_STATE
1750 = sm
->get_state_by_name ("unchecked");
1751 auto_delete_vec
<state_machine
> checkers
;
1752 checkers
.safe_push (sm
);
1755 extrinsic_state
ext_state (checkers
, &eng
);
1756 region_model_manager
*mgr
= eng
.get_model_manager ();
1757 program_state
s (ext_state
);
1758 region_model
*model
= s
.m_region_model
;
1759 const svalue
*size_in_bytes
1760 = mgr
->get_or_create_unknown_svalue (size_type_node
);
1761 const region
*new_reg
1762 = model
->get_or_create_region_for_heap_alloc (size_in_bytes
, NULL
);
1763 const svalue
*ptr_sval
= mgr
->get_ptr_svalue (ptr_type_node
, new_reg
);
1764 model
->set_value (model
->get_lvalue (p
, NULL
),
1766 sm_state_map
*smap
= s
.m_checker_states
[0];
1768 smap
->impl_set_state (ptr_sval
, UNCHECKED_STATE
, NULL
, ext_state
);
1769 ASSERT_EQ (smap
->get_state (ptr_sval
, ext_state
), UNCHECKED_STATE
);
1772 /* Check that program_state works for string literals. */
1775 test_program_state_2 ()
1777 /* Create a program_state for a global ptr "p" that points to
1778 a string constant. */
1779 tree p
= build_global_decl ("p", ptr_type_node
);
1781 tree string_cst_ptr
= build_string_literal (4, "foo");
1783 auto_delete_vec
<state_machine
> checkers
;
1785 extrinsic_state
ext_state (checkers
, &eng
);
1787 program_state
s (ext_state
);
1788 region_model
*model
= s
.m_region_model
;
1789 const region
*p_reg
= model
->get_lvalue (p
, NULL
);
1790 const svalue
*str_sval
= model
->get_rvalue (string_cst_ptr
, NULL
);
1791 model
->set_value (p_reg
, str_sval
, NULL
);
1794 /* Verify that program_states with identical sm-state can be merged,
1795 and that the merged program_state preserves the sm-state. */
1798 test_program_state_merging ()
1800 /* Create a program_state for a global ptr "p" that has
1801 malloc sm-state, pointing to a region on the heap. */
1802 tree p
= build_global_decl ("p", ptr_type_node
);
1805 region_model_manager
*mgr
= eng
.get_model_manager ();
1806 program_point
point (program_point::origin (*mgr
));
1807 auto_delete_vec
<state_machine
> checkers
;
1808 checkers
.safe_push (make_malloc_state_machine (NULL
));
1809 extrinsic_state
ext_state (checkers
, &eng
);
1811 program_state
s0 (ext_state
);
1812 uncertainty_t uncertainty
;
1813 impl_region_model_context
ctxt (&s0
, ext_state
, &uncertainty
);
1815 region_model
*model0
= s0
.m_region_model
;
1816 const svalue
*size_in_bytes
1817 = mgr
->get_or_create_unknown_svalue (size_type_node
);
1818 const region
*new_reg
1819 = model0
->get_or_create_region_for_heap_alloc (size_in_bytes
, NULL
);
1820 const svalue
*ptr_sval
= mgr
->get_ptr_svalue (ptr_type_node
, new_reg
);
1821 model0
->set_value (model0
->get_lvalue (p
, &ctxt
),
1823 sm_state_map
*smap
= s0
.m_checker_states
[0];
1824 const state_machine::state
test_state ("test state", 0);
1825 const state_machine::state_t TEST_STATE
= &test_state
;
1826 smap
->impl_set_state (ptr_sval
, TEST_STATE
, NULL
, ext_state
);
1827 ASSERT_EQ (smap
->get_state (ptr_sval
, ext_state
), TEST_STATE
);
1829 model0
->canonicalize ();
1831 /* Verify that canonicalization preserves sm-state. */
1832 ASSERT_EQ (smap
->get_state (model0
->get_rvalue (p
, NULL
), ext_state
),
1835 /* Make a copy of the program_state. */
1836 program_state
s1 (s0
);
1839 /* We have two identical states with "p" pointing to a heap region
1840 with the given sm-state.
1841 They ought to be mergeable, preserving the sm-state. */
1842 program_state
merged (ext_state
);
1843 ASSERT_TRUE (s0
.can_merge_with_p (s1
, ext_state
, point
, &merged
));
1844 merged
.validate (ext_state
);
1846 /* Verify that the merged state has the sm-state for "p". */
1847 region_model
*merged_model
= merged
.m_region_model
;
1848 sm_state_map
*merged_smap
= merged
.m_checker_states
[0];
1849 ASSERT_EQ (merged_smap
->get_state (merged_model
->get_rvalue (p
, NULL
),
1853 /* Try canonicalizing. */
1854 merged
.m_region_model
->canonicalize ();
1855 merged
.validate (ext_state
);
1857 /* Verify that the merged state still has the sm-state for "p". */
1858 ASSERT_EQ (merged_smap
->get_state (merged_model
->get_rvalue (p
, NULL
),
1862 /* After canonicalization, we ought to have equality with the inputs. */
1863 ASSERT_EQ (s0
, merged
);
1866 /* Verify that program_states with different global-state in an sm-state
1870 test_program_state_merging_2 ()
1873 region_model_manager
*mgr
= eng
.get_model_manager ();
1874 program_point
point (program_point::origin (*mgr
));
1875 auto_delete_vec
<state_machine
> checkers
;
1876 checkers
.safe_push (make_signal_state_machine (NULL
));
1877 extrinsic_state
ext_state (checkers
, &eng
);
1879 const state_machine::state
test_state_0 ("test state 0", 0);
1880 const state_machine::state
test_state_1 ("test state 1", 1);
1881 const state_machine::state_t TEST_STATE_0
= &test_state_0
;
1882 const state_machine::state_t TEST_STATE_1
= &test_state_1
;
1884 program_state
s0 (ext_state
);
1886 sm_state_map
*smap0
= s0
.m_checker_states
[0];
1887 smap0
->set_global_state (TEST_STATE_0
);
1888 ASSERT_EQ (smap0
->get_global_state (), TEST_STATE_0
);
1891 program_state
s1 (ext_state
);
1893 sm_state_map
*smap1
= s1
.m_checker_states
[0];
1894 smap1
->set_global_state (TEST_STATE_1
);
1895 ASSERT_EQ (smap1
->get_global_state (), TEST_STATE_1
);
1900 /* They ought to not be mergeable. */
1901 program_state
merged (ext_state
);
1902 ASSERT_FALSE (s0
.can_merge_with_p (s1
, ext_state
, point
, &merged
));
1905 /* Run all of the selftests within this file. */
1908 analyzer_program_state_cc_tests ()
1910 test_sm_state_map ();
1911 test_program_state_1 ();
1912 test_program_state_2 ();
1913 test_program_state_merging ();
1914 test_program_state_merging_2 ();
1917 } // namespace selftest
1919 #endif /* CHECKING_P */
1923 #endif /* #if ENABLE_ANALYZER */