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 std::unique_ptr
<rejected_constraint
> rc
;
1149 logger
* const logger
= eg
.get_logger ();
1150 if (!m_region_model
->maybe_update_for_edge (*succ
,
1153 logger
? &rc
: nullptr))
1157 logger
->start_log_line ();
1158 logger
->log_partial ("edge to SN: %i is impossible"
1159 " due to region_model constraint: ",
1160 succ
->m_dest
->m_index
);
1161 rc
->dump_to_pp (logger
->get_printer ());
1162 logger
->end_log_line ();
1169 program_state::detect_leaks (enode
->get_state (), *this,
1170 NULL
, eg
.get_ext_state (),
1176 /* Update this program_state to reflect a call to function
1177 represented by CALL_STMT.
1178 currently used only when the call doesn't have a superedge representing
1179 the call ( like call via a function pointer ) */
1181 program_state::push_call (exploded_graph
&eg
,
1182 exploded_node
*enode
,
1183 const gcall
*call_stmt
,
1184 uncertainty_t
*uncertainty
)
1187 const program_point
&point
= enode
->get_point ();
1188 const gimple
*last_stmt
= point
.get_supernode ()->get_last_stmt ();
1190 impl_region_model_context
ctxt (eg
, enode
,
1191 &enode
->get_state (),
1196 m_region_model
->update_for_gcall (call_stmt
, &ctxt
);
1199 /* Update this program_state to reflect a return from function
1200 call to which is represented by CALL_STMT.
1201 currently used only when the call doesn't have a superedge representing
1204 program_state::returning_call (exploded_graph
&eg
,
1205 exploded_node
*enode
,
1206 const gcall
*call_stmt
,
1207 uncertainty_t
*uncertainty
)
1210 const program_point
&point
= enode
->get_point ();
1211 const gimple
*last_stmt
= point
.get_supernode ()->get_last_stmt ();
1213 impl_region_model_context
ctxt (eg
, enode
,
1214 &enode
->get_state (),
1219 m_region_model
->update_for_return_gcall (call_stmt
, &ctxt
);
1222 /* Generate a simpler version of THIS, discarding state that's no longer
1224 The idea is that we're more likely to be able to consolidate
1225 multiple (point, state) into single exploded_nodes if we discard
1226 irrelevant state (e.g. at the end of functions). */
1229 program_state::prune_for_point (exploded_graph
&eg
,
1230 const program_point
&point
,
1231 exploded_node
*enode_for_diag
,
1232 uncertainty_t
*uncertainty
) const
1234 logger
* const logger
= eg
.get_logger ();
1237 function
*fun
= point
.get_function ();
1241 program_state
new_state (*this);
1243 const state_purge_map
*pm
= eg
.get_purge_map ();
1246 unsigned num_ssas_purged
= 0;
1247 unsigned num_decls_purged
= 0;
1248 auto_vec
<const decl_region
*> regs
;
1249 new_state
.m_region_model
->get_regions_for_current_frame (®s
);
1250 regs
.qsort (region::cmp_ptr_ptr
);
1252 const decl_region
*reg
;
1253 FOR_EACH_VEC_ELT (regs
, i
, reg
)
1255 const tree node
= reg
->get_decl ();
1256 if (TREE_CODE (node
) == SSA_NAME
)
1258 const tree ssa_name
= node
;
1259 const state_purge_per_ssa_name
&per_ssa
1260 = pm
->get_data_for_ssa_name (node
);
1261 if (!per_ssa
.needed_at_point_p (point
.get_function_point ()))
1263 /* Don't purge bindings of SSA names to svalues
1264 that have unpurgable sm-state, so that leaks are
1265 reported at the end of the function, rather than
1266 at the last place that such an SSA name is referred to.
1268 But do purge them for temporaries (when SSA_NAME_VAR is
1269 NULL), so that we report for cases where a leak happens when
1270 a variable is overwritten with another value, so that the leak
1271 is reported at the point of overwrite, rather than having
1272 temporaries keep the value reachable until the frame is
1275 = new_state
.m_region_model
->get_store_value (reg
, NULL
);
1276 if (!new_state
.can_purge_p (eg
.get_ext_state (), sval
)
1277 && SSA_NAME_VAR (ssa_name
))
1279 /* (currently only state maps can keep things
1282 logger
->log ("not purging binding for %qE"
1283 " (used by state map)", ssa_name
);
1287 new_state
.m_region_model
->purge_region (reg
);
1293 const tree decl
= node
;
1294 gcc_assert (TREE_CODE (node
) == VAR_DECL
1295 || TREE_CODE (node
) == PARM_DECL
1296 || TREE_CODE (node
) == RESULT_DECL
);
1297 if (const state_purge_per_decl
*per_decl
1298 = pm
->get_any_data_for_decl (decl
))
1299 if (!per_decl
->needed_at_point_p (point
.get_function_point ()))
1301 /* Don't purge bindings of decls if there are svalues
1302 that have unpurgable sm-state within the decl's cluster,
1303 so that leaks are reported at the end of the function,
1304 rather than at the last place that such a decl is
1306 if (!new_state
.can_purge_base_region_p (eg
.get_ext_state (),
1309 /* (currently only state maps can keep things
1312 logger
->log ("not purging binding for %qE"
1313 " (value in binding used by state map)",
1318 new_state
.m_region_model
->purge_region (reg
);
1324 if (num_ssas_purged
> 0 || num_decls_purged
> 0)
1328 logger
->log ("num_ssas_purged: %i", num_ssas_purged
);
1329 logger
->log ("num_decl_purged: %i", num_decls_purged
);
1331 impl_region_model_context
ctxt (eg
, enode_for_diag
,
1336 detect_leaks (*this, new_state
, NULL
, eg
.get_ext_state (), &ctxt
);
1340 new_state
.m_region_model
->canonicalize ();
1345 /* Return true if there are no unpurgeable bindings within BASE_REG. */
1348 program_state::can_purge_base_region_p (const extrinsic_state
&ext_state
,
1349 const region
*base_reg
) const
1351 binding_cluster
*cluster
1352 = m_region_model
->get_store ()->get_cluster (base_reg
);
1356 for (auto iter
: *cluster
)
1358 const svalue
*sval
= iter
.second
;
1359 if (!can_purge_p (ext_state
, sval
))
1366 /* Get a representative tree to use for describing SVAL. */
1369 program_state::get_representative_tree (const svalue
*sval
) const
1371 gcc_assert (m_region_model
);
1372 return m_region_model
->get_representative_tree (sval
);
1375 /* Attempt to merge this state with OTHER, both at POINT.
1376 Write the result to *OUT.
1377 If the states were merged successfully, return true. */
1380 program_state::can_merge_with_p (const program_state
&other
,
1381 const extrinsic_state
&ext_state
,
1382 const program_point
&point
,
1383 program_state
*out
) const
1386 gcc_assert (m_region_model
);
1388 /* Attempt to merge the sm-states. */
1391 FOR_EACH_VEC_ELT (out
->m_checker_states
, i
, smap
)
1392 if (!m_checker_states
[i
]->can_merge_with_p (*other
.m_checker_states
[i
],
1393 ext_state
.get_sm (i
),
1395 &out
->m_checker_states
[i
]))
1398 /* Attempt to merge the region_models. */
1399 if (!m_region_model
->can_merge_with_p (*other
.m_region_model
,
1401 out
->m_region_model
,
1406 out
->m_region_model
->canonicalize ();
1411 /* Assert that this object is valid. */
1414 program_state::validate (const extrinsic_state
&ext_state
) const
1416 /* Skip this in a release build. */
1421 gcc_assert (m_checker_states
.length () == ext_state
.get_num_checkers ());
1422 m_region_model
->validate ();
1426 log_set_of_svalues (logger
*logger
, const char *name
,
1427 const svalue_set
&set
)
1430 logger
->inc_indent ();
1431 auto_vec
<const svalue
*> sval_vecs (set
.elements ());
1432 for (svalue_set::iterator iter
= set
.begin ();
1433 iter
!= set
.end (); ++iter
)
1434 sval_vecs
.quick_push (*iter
);
1435 sval_vecs
.qsort (svalue::cmp_ptr_ptr
);
1438 FOR_EACH_VEC_ELT (sval_vecs
, i
, sval
)
1440 logger
->start_log_line ();
1441 pretty_printer
*pp
= logger
->get_printer ();
1442 if (!flag_dump_noaddr
)
1444 pp_pointer (pp
, sval
);
1445 pp_string (pp
, ": ");
1447 sval
->dump_to_pp (pp
, false);
1448 logger
->end_log_line ();
1450 logger
->dec_indent ();
1453 /* Compare the sets of svalues reachable from each of SRC_STATE and DEST_STATE.
1454 For all svalues that are reachable in SRC_STATE and are not live in
1455 DEST_STATE (whether explicitly reachable in DEST_STATE, or implicitly live
1456 based on the former set), call CTXT->on_svalue_leak for them.
1458 Call on_liveness_change on both the CTXT and on the DEST_STATE's
1459 constraint_manager, purging dead svalues from sm-state and from
1460 constraints, respectively.
1462 This function should be called at each fine-grained state change, not
1463 just at exploded edges. */
1466 program_state::detect_leaks (const program_state
&src_state
,
1467 const program_state
&dest_state
,
1468 const svalue
*extra_sval
,
1469 const extrinsic_state
&ext_state
,
1470 region_model_context
*ctxt
)
1472 logger
*logger
= ext_state
.get_logger ();
1474 const uncertainty_t
*uncertainty
= ctxt
->get_uncertainty ();
1477 pretty_printer
*pp
= logger
->get_printer ();
1478 logger
->start_log_line ();
1479 pp_string (pp
, "src_state: ");
1480 src_state
.dump_to_pp (ext_state
, true, false, pp
);
1481 logger
->end_log_line ();
1482 logger
->start_log_line ();
1483 pp_string (pp
, "dest_state: ");
1484 dest_state
.dump_to_pp (ext_state
, true, false, pp
);
1485 logger
->end_log_line ();
1488 logger
->start_log_line ();
1489 pp_string (pp
, "extra_sval: ");
1490 extra_sval
->dump_to_pp (pp
, true);
1491 logger
->end_log_line ();
1495 logger
->start_log_line ();
1496 pp_string (pp
, "uncertainty: ");
1497 uncertainty
->dump_to_pp (pp
, true);
1498 logger
->end_log_line ();
1502 /* Get svalues reachable from each of src_state and dest_state.
1503 Get svalues *known* to be reachable in src_state.
1504 Pass in uncertainty for dest_state so that we additionally get svalues that
1505 *might* still be reachable in dst_state. */
1506 svalue_set known_src_svalues
;
1507 src_state
.m_region_model
->get_reachable_svalues (&known_src_svalues
,
1509 svalue_set maybe_dest_svalues
;
1510 dest_state
.m_region_model
->get_reachable_svalues (&maybe_dest_svalues
,
1511 extra_sval
, uncertainty
);
1515 log_set_of_svalues (logger
, "src_state known reachable svalues:",
1517 log_set_of_svalues (logger
, "dest_state maybe reachable svalues:",
1518 maybe_dest_svalues
);
1521 auto_vec
<const svalue
*> dead_svals (known_src_svalues
.elements ());
1522 for (svalue_set::iterator iter
= known_src_svalues
.begin ();
1523 iter
!= known_src_svalues
.end (); ++iter
)
1525 const svalue
*sval
= (*iter
);
1526 /* For each sval reachable from SRC_STATE, determine if it is
1527 live in DEST_STATE: either explicitly reachable, implicitly
1528 live based on the set of explicitly reachable svalues,
1529 or possibly reachable as recorded in uncertainty.
1530 Record those that have ceased to be live i.e. were known
1531 to be live, and are now not known to be even possibly-live. */
1532 if (!sval
->live_p (&maybe_dest_svalues
, dest_state
.m_region_model
))
1533 dead_svals
.quick_push (sval
);
1536 /* Call CTXT->on_svalue_leak on all svals in SRC_STATE that have ceased
1537 to be live, sorting them first to ensure deterministic behavior. */
1538 dead_svals
.qsort (svalue::cmp_ptr_ptr
);
1541 FOR_EACH_VEC_ELT (dead_svals
, i
, sval
)
1542 ctxt
->on_svalue_leak (sval
);
1544 /* Purge dead svals from sm-state. */
1545 ctxt
->on_liveness_change (maybe_dest_svalues
,
1546 dest_state
.m_region_model
);
1548 /* Purge dead svals from constraints. */
1549 dest_state
.m_region_model
->get_constraints ()->on_liveness_change
1550 (maybe_dest_svalues
, dest_state
.m_region_model
);
1552 /* Purge dead heap-allocated regions from dynamic extents. */
1553 for (const svalue
*sval
: dead_svals
)
1554 if (const region
*reg
= sval
->maybe_get_region ())
1555 if (reg
->get_kind () == RK_HEAP_ALLOCATED
)
1556 dest_state
.m_region_model
->unset_dynamic_extents (reg
);
1559 /* Attempt to to use R to replay SUMMARY into this object.
1560 Return true if it is possible. */
1563 program_state::replay_call_summary (call_summary_replay
&r
,
1564 const program_state
&summary
)
1566 if (!m_region_model
->replay_call_summary (r
, *summary
.m_region_model
))
1569 for (unsigned sm_idx
= 0; sm_idx
< m_checker_states
.length (); sm_idx
++)
1571 const sm_state_map
*summary_sm_map
= summary
.m_checker_states
[sm_idx
];
1572 m_checker_states
[sm_idx
]->replay_call_summary (r
, *summary_sm_map
);
1575 if (!summary
.m_valid
)
1581 /* Handle calls to "__analyzer_dump_state". */
1584 program_state::impl_call_analyzer_dump_state (const gcall
*call
,
1585 const extrinsic_state
&ext_state
,
1586 region_model_context
*ctxt
)
1588 call_details
cd (call
, m_region_model
, ctxt
);
1589 const char *sm_name
= cd
.get_arg_string_literal (0);
1592 error_at (call
->location
, "cannot determine state machine");
1596 if (!ext_state
.get_sm_idx_by_name (sm_name
, &sm_idx
))
1598 error_at (call
->location
, "unrecognized state machine %qs", sm_name
);
1601 const sm_state_map
*smap
= m_checker_states
[sm_idx
];
1603 const svalue
*sval
= cd
.get_arg_svalue (1);
1605 /* Strip off cast to int (due to variadic args). */
1606 if (const svalue
*cast
= sval
->maybe_undo_cast ())
1609 state_machine::state_t state
= smap
->get_state (sval
, ext_state
);
1610 warning_at (call
->location
, 0, "state: %qs", state
->get_name ());
1615 namespace selftest
{
1617 /* Tests for sm_state_map. */
1620 test_sm_state_map ()
1622 tree x
= build_global_decl ("x", integer_type_node
);
1623 tree y
= build_global_decl ("y", integer_type_node
);
1624 tree z
= build_global_decl ("z", integer_type_node
);
1626 state_machine
*sm
= make_malloc_state_machine (NULL
);
1627 auto_delete_vec
<state_machine
> checkers
;
1628 checkers
.safe_push (sm
);
1630 extrinsic_state
ext_state (checkers
, &eng
);
1631 state_machine::state_t start
= sm
->get_start_state ();
1633 /* Test setting states on svalue_id instances directly. */
1635 const state_machine::state
test_state_42 ("test state 42", 42);
1636 const state_machine::state_t TEST_STATE_42
= &test_state_42
;
1637 region_model_manager mgr
;
1638 region_model
model (&mgr
);
1639 const svalue
*x_sval
= model
.get_rvalue (x
, NULL
);
1640 const svalue
*y_sval
= model
.get_rvalue (y
, NULL
);
1641 const svalue
*z_sval
= model
.get_rvalue (z
, NULL
);
1643 sm_state_map
map (*sm
);
1644 ASSERT_TRUE (map
.is_empty_p ());
1645 ASSERT_EQ (map
.get_state (x_sval
, ext_state
), start
);
1647 map
.impl_set_state (x_sval
, TEST_STATE_42
, z_sval
, ext_state
);
1648 ASSERT_EQ (map
.get_state (x_sval
, ext_state
), TEST_STATE_42
);
1649 ASSERT_EQ (map
.get_origin (x_sval
, ext_state
), z_sval
);
1650 ASSERT_EQ (map
.get_state (y_sval
, ext_state
), start
);
1651 ASSERT_FALSE (map
.is_empty_p ());
1653 map
.impl_set_state (y_sval
, 0, z_sval
, ext_state
);
1654 ASSERT_EQ (map
.get_state (y_sval
, ext_state
), start
);
1656 map
.impl_set_state (x_sval
, 0, z_sval
, ext_state
);
1657 ASSERT_EQ (map
.get_state (x_sval
, ext_state
), start
);
1658 ASSERT_TRUE (map
.is_empty_p ());
1661 const state_machine::state
test_state_5 ("test state 5", 5);
1662 const state_machine::state_t TEST_STATE_5
= &test_state_5
;
1664 /* Test setting states via equivalence classes. */
1666 region_model_manager mgr
;
1667 region_model
model (&mgr
);
1668 const svalue
*x_sval
= model
.get_rvalue (x
, NULL
);
1669 const svalue
*y_sval
= model
.get_rvalue (y
, NULL
);
1670 const svalue
*z_sval
= model
.get_rvalue (z
, NULL
);
1672 sm_state_map
map (*sm
);
1673 ASSERT_TRUE (map
.is_empty_p ());
1674 ASSERT_EQ (map
.get_state (x_sval
, ext_state
), start
);
1675 ASSERT_EQ (map
.get_state (y_sval
, ext_state
), start
);
1677 model
.add_constraint (x
, EQ_EXPR
, y
, NULL
);
1679 /* Setting x to a state should also update y, as they
1680 are in the same equivalence class. */
1681 map
.set_state (&model
, x_sval
, TEST_STATE_5
, z_sval
, ext_state
);
1682 ASSERT_EQ (map
.get_state (x_sval
, ext_state
), TEST_STATE_5
);
1683 ASSERT_EQ (map
.get_state (y_sval
, ext_state
), TEST_STATE_5
);
1684 ASSERT_EQ (map
.get_origin (x_sval
, ext_state
), z_sval
);
1685 ASSERT_EQ (map
.get_origin (y_sval
, ext_state
), z_sval
);
1688 /* Test equality and hashing. */
1690 region_model_manager mgr
;
1691 region_model
model (&mgr
);
1692 const svalue
*y_sval
= model
.get_rvalue (y
, NULL
);
1693 const svalue
*z_sval
= model
.get_rvalue (z
, NULL
);
1695 sm_state_map
map0 (*sm
);
1696 sm_state_map
map1 (*sm
);
1697 sm_state_map
map2 (*sm
);
1699 ASSERT_EQ (map0
.hash (), map1
.hash ());
1700 ASSERT_EQ (map0
, map1
);
1702 map1
.impl_set_state (y_sval
, TEST_STATE_5
, z_sval
, ext_state
);
1703 ASSERT_NE (map0
.hash (), map1
.hash ());
1704 ASSERT_NE (map0
, map1
);
1706 /* Make the same change to map2. */
1707 map2
.impl_set_state (y_sval
, TEST_STATE_5
, z_sval
, ext_state
);
1708 ASSERT_EQ (map1
.hash (), map2
.hash ());
1709 ASSERT_EQ (map1
, map2
);
1712 /* Equality and hashing shouldn't depend on ordering. */
1714 const state_machine::state
test_state_2 ("test state 2", 2);
1715 const state_machine::state_t TEST_STATE_2
= &test_state_2
;
1716 const state_machine::state
test_state_3 ("test state 3", 3);
1717 const state_machine::state_t TEST_STATE_3
= &test_state_3
;
1718 sm_state_map
map0 (*sm
);
1719 sm_state_map
map1 (*sm
);
1720 sm_state_map
map2 (*sm
);
1722 ASSERT_EQ (map0
.hash (), map1
.hash ());
1723 ASSERT_EQ (map0
, map1
);
1725 region_model_manager mgr
;
1726 region_model
model (&mgr
);
1727 const svalue
*x_sval
= model
.get_rvalue (x
, NULL
);
1728 const svalue
*y_sval
= model
.get_rvalue (y
, NULL
);
1729 const svalue
*z_sval
= model
.get_rvalue (z
, NULL
);
1731 map1
.impl_set_state (x_sval
, TEST_STATE_2
, NULL
, ext_state
);
1732 map1
.impl_set_state (y_sval
, TEST_STATE_3
, NULL
, ext_state
);
1733 map1
.impl_set_state (z_sval
, TEST_STATE_2
, NULL
, ext_state
);
1735 map2
.impl_set_state (z_sval
, TEST_STATE_2
, NULL
, ext_state
);
1736 map2
.impl_set_state (y_sval
, TEST_STATE_3
, NULL
, ext_state
);
1737 map2
.impl_set_state (x_sval
, TEST_STATE_2
, NULL
, ext_state
);
1739 ASSERT_EQ (map1
.hash (), map2
.hash ());
1740 ASSERT_EQ (map1
, map2
);
1743 // TODO: coverage for purging
1746 /* Check program_state works as expected. */
1749 test_program_state_1 ()
1751 /* Create a program_state for a global ptr "p" that has
1752 malloc sm-state, pointing to a region on the heap. */
1753 tree p
= build_global_decl ("p", ptr_type_node
);
1755 state_machine
*sm
= make_malloc_state_machine (NULL
);
1756 const state_machine::state_t UNCHECKED_STATE
1757 = sm
->get_state_by_name ("unchecked");
1758 auto_delete_vec
<state_machine
> checkers
;
1759 checkers
.safe_push (sm
);
1762 extrinsic_state
ext_state (checkers
, &eng
);
1763 region_model_manager
*mgr
= eng
.get_model_manager ();
1764 program_state
s (ext_state
);
1765 region_model
*model
= s
.m_region_model
;
1766 const svalue
*size_in_bytes
1767 = mgr
->get_or_create_unknown_svalue (size_type_node
);
1768 const region
*new_reg
1769 = model
->get_or_create_region_for_heap_alloc (size_in_bytes
, NULL
);
1770 const svalue
*ptr_sval
= mgr
->get_ptr_svalue (ptr_type_node
, new_reg
);
1771 model
->set_value (model
->get_lvalue (p
, NULL
),
1773 sm_state_map
*smap
= s
.m_checker_states
[0];
1775 smap
->impl_set_state (ptr_sval
, UNCHECKED_STATE
, NULL
, ext_state
);
1776 ASSERT_EQ (smap
->get_state (ptr_sval
, ext_state
), UNCHECKED_STATE
);
1779 /* Check that program_state works for string literals. */
1782 test_program_state_2 ()
1784 /* Create a program_state for a global ptr "p" that points to
1785 a string constant. */
1786 tree p
= build_global_decl ("p", ptr_type_node
);
1788 tree string_cst_ptr
= build_string_literal (4, "foo");
1790 auto_delete_vec
<state_machine
> checkers
;
1792 extrinsic_state
ext_state (checkers
, &eng
);
1794 program_state
s (ext_state
);
1795 region_model
*model
= s
.m_region_model
;
1796 const region
*p_reg
= model
->get_lvalue (p
, NULL
);
1797 const svalue
*str_sval
= model
->get_rvalue (string_cst_ptr
, NULL
);
1798 model
->set_value (p_reg
, str_sval
, NULL
);
1801 /* Verify that program_states with identical sm-state can be merged,
1802 and that the merged program_state preserves the sm-state. */
1805 test_program_state_merging ()
1807 /* Create a program_state for a global ptr "p" that has
1808 malloc sm-state, pointing to a region on the heap. */
1809 tree p
= build_global_decl ("p", ptr_type_node
);
1812 region_model_manager
*mgr
= eng
.get_model_manager ();
1813 program_point
point (program_point::origin (*mgr
));
1814 auto_delete_vec
<state_machine
> checkers
;
1815 checkers
.safe_push (make_malloc_state_machine (NULL
));
1816 extrinsic_state
ext_state (checkers
, &eng
);
1818 program_state
s0 (ext_state
);
1819 uncertainty_t uncertainty
;
1820 impl_region_model_context
ctxt (&s0
, ext_state
, &uncertainty
);
1822 region_model
*model0
= s0
.m_region_model
;
1823 const svalue
*size_in_bytes
1824 = mgr
->get_or_create_unknown_svalue (size_type_node
);
1825 const region
*new_reg
1826 = model0
->get_or_create_region_for_heap_alloc (size_in_bytes
, NULL
);
1827 const svalue
*ptr_sval
= mgr
->get_ptr_svalue (ptr_type_node
, new_reg
);
1828 model0
->set_value (model0
->get_lvalue (p
, &ctxt
),
1830 sm_state_map
*smap
= s0
.m_checker_states
[0];
1831 const state_machine::state
test_state ("test state", 0);
1832 const state_machine::state_t TEST_STATE
= &test_state
;
1833 smap
->impl_set_state (ptr_sval
, TEST_STATE
, NULL
, ext_state
);
1834 ASSERT_EQ (smap
->get_state (ptr_sval
, ext_state
), TEST_STATE
);
1836 model0
->canonicalize ();
1838 /* Verify that canonicalization preserves sm-state. */
1839 ASSERT_EQ (smap
->get_state (model0
->get_rvalue (p
, NULL
), ext_state
),
1842 /* Make a copy of the program_state. */
1843 program_state
s1 (s0
);
1846 /* We have two identical states with "p" pointing to a heap region
1847 with the given sm-state.
1848 They ought to be mergeable, preserving the sm-state. */
1849 program_state
merged (ext_state
);
1850 ASSERT_TRUE (s0
.can_merge_with_p (s1
, ext_state
, point
, &merged
));
1851 merged
.validate (ext_state
);
1853 /* Verify that the merged state has the sm-state for "p". */
1854 region_model
*merged_model
= merged
.m_region_model
;
1855 sm_state_map
*merged_smap
= merged
.m_checker_states
[0];
1856 ASSERT_EQ (merged_smap
->get_state (merged_model
->get_rvalue (p
, NULL
),
1860 /* Try canonicalizing. */
1861 merged
.m_region_model
->canonicalize ();
1862 merged
.validate (ext_state
);
1864 /* Verify that the merged state still has the sm-state for "p". */
1865 ASSERT_EQ (merged_smap
->get_state (merged_model
->get_rvalue (p
, NULL
),
1869 /* After canonicalization, we ought to have equality with the inputs. */
1870 ASSERT_EQ (s0
, merged
);
1873 /* Verify that program_states with different global-state in an sm-state
1877 test_program_state_merging_2 ()
1880 region_model_manager
*mgr
= eng
.get_model_manager ();
1881 program_point
point (program_point::origin (*mgr
));
1882 auto_delete_vec
<state_machine
> checkers
;
1883 checkers
.safe_push (make_signal_state_machine (NULL
));
1884 extrinsic_state
ext_state (checkers
, &eng
);
1886 const state_machine::state
test_state_0 ("test state 0", 0);
1887 const state_machine::state
test_state_1 ("test state 1", 1);
1888 const state_machine::state_t TEST_STATE_0
= &test_state_0
;
1889 const state_machine::state_t TEST_STATE_1
= &test_state_1
;
1891 program_state
s0 (ext_state
);
1893 sm_state_map
*smap0
= s0
.m_checker_states
[0];
1894 smap0
->set_global_state (TEST_STATE_0
);
1895 ASSERT_EQ (smap0
->get_global_state (), TEST_STATE_0
);
1898 program_state
s1 (ext_state
);
1900 sm_state_map
*smap1
= s1
.m_checker_states
[0];
1901 smap1
->set_global_state (TEST_STATE_1
);
1902 ASSERT_EQ (smap1
->get_global_state (), TEST_STATE_1
);
1907 /* They ought to not be mergeable. */
1908 program_state
merged (ext_state
);
1909 ASSERT_FALSE (s0
.can_merge_with_p (s1
, ext_state
, point
, &merged
));
1912 /* Run all of the selftests within this file. */
1915 analyzer_program_state_cc_tests ()
1917 test_sm_state_map ();
1918 test_program_state_1 ();
1919 test_program_state_2 ();
1920 test_program_state_merging ();
1921 test_program_state_merging_2 ();
1924 } // namespace selftest
1926 #endif /* CHECKING_P */
1930 #endif /* #if ENABLE_ANALYZER */