1 /* Classes for representing the state of interest at a given path of analysis.
2 Copyright (C) 2019-2021 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/>. */
23 #include "coretypes.h"
25 #include "diagnostic-core.h"
26 #include "diagnostic.h"
29 #include "analyzer/analyzer.h"
30 #include "analyzer/analyzer-logging.h"
31 #include "analyzer/sm.h"
35 #include "ordered-hash-map.h"
37 #include "analyzer/call-string.h"
38 #include "analyzer/program-point.h"
39 #include "analyzer/store.h"
40 #include "analyzer/region-model.h"
41 #include "analyzer/program-state.h"
42 #include "analyzer/constraint-manager.h"
43 #include "alloc-pool.h"
44 #include "fibonacci_heap.h"
45 #include "shortest-paths.h"
46 #include "diagnostic-event-id.h"
47 #include "analyzer/pending-diagnostic.h"
48 #include "analyzer/diagnostic-manager.h"
50 #include "basic-block.h"
52 #include "gimple-iterator.h"
55 #include "analyzer/supergraph.h"
56 #include "analyzer/program-state.h"
57 #include "analyzer/exploded-graph.h"
58 #include "analyzer/state-purge.h"
59 #include "analyzer/analyzer-selftests.h"
65 /* class extrinsic_state. */
67 /* Dump a multiline representation of this state to PP. */
70 extrinsic_state::dump_to_pp (pretty_printer
*pp
) const
72 pp_printf (pp
, "extrinsic_state: %i checker(s)\n", get_num_checkers ());
74 state_machine
*checker
;
75 FOR_EACH_VEC_ELT (m_checkers
, i
, checker
)
77 pp_printf (pp
, "m_checkers[%i]: %qs\n", i
, checker
->get_name ());
78 checker
->dump_to_pp (pp
);
82 /* Dump a multiline representation of this state to OUTF. */
85 extrinsic_state::dump_to_file (FILE *outf
) const
89 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
90 pp
.buffer
->stream
= outf
;
95 /* Dump a multiline representation of this state to stderr. */
98 extrinsic_state::dump () const
100 dump_to_file (stderr
);
103 /* Return a new json::object of the form
104 {"checkers" : array of objects, one for each state_machine}. */
107 extrinsic_state::to_json () const
109 json::object
*ext_state_obj
= new json::object ();
112 json::array
*checkers_arr
= new json::array ();
115 FOR_EACH_VEC_ELT (m_checkers
, i
, sm
)
116 checkers_arr
->append (sm
->to_json ());
117 ext_state_obj
->set ("checkers", checkers_arr
);
120 return ext_state_obj
;
123 /* Get the region_model_manager for this extrinsic_state. */
125 region_model_manager
*
126 extrinsic_state::get_model_manager () const
129 return m_engine
->get_model_manager ();
131 return NULL
; /* for selftests. */
134 /* Try to find a state machine named NAME.
135 If found, return true and write its index to *OUT.
136 Otherwise return false. */
139 extrinsic_state::get_sm_idx_by_name (const char *name
, unsigned *out
) const
143 FOR_EACH_VEC_ELT (m_checkers
, i
, sm
)
144 if (0 == strcmp (name
, sm
->get_name ()))
151 /* NAME not found. */
155 /* struct sm_state_map::entry_t. */
158 sm_state_map::entry_t::cmp (const entry_t
&entry_a
, const entry_t
&entry_b
)
160 gcc_assert (entry_a
.m_state
);
161 gcc_assert (entry_b
.m_state
);
162 if (int cmp_state
= ((int)entry_a
.m_state
->get_id ()
163 - (int)entry_b
.m_state
->get_id ()))
165 if (entry_a
.m_origin
&& entry_b
.m_origin
)
166 return svalue::cmp_ptr (entry_a
.m_origin
, entry_b
.m_origin
);
167 if (entry_a
.m_origin
)
169 if (entry_b
.m_origin
)
174 /* class sm_state_map. */
176 /* sm_state_map's ctor. */
178 sm_state_map::sm_state_map (const state_machine
&sm
)
179 : m_sm (sm
), m_map (), m_global_state (sm
.get_start_state ())
183 /* Clone the sm_state_map. */
186 sm_state_map::clone () const
188 return new sm_state_map (*this);
191 /* Print this sm_state_map to PP.
192 If MODEL is non-NULL, print representative tree values where
196 sm_state_map::print (const region_model
*model
,
197 bool simple
, bool multiline
,
198 pretty_printer
*pp
) const
203 if (m_global_state
!= m_sm
.get_start_state ())
207 pp_string (pp
, "global: ");
208 m_global_state
->dump_to_pp (pp
);
213 auto_vec
<const svalue
*> keys (m_map
.elements ());
214 for (map_t::iterator iter
= m_map
.begin ();
215 iter
!= m_map
.end ();
217 keys
.quick_push ((*iter
).first
);
218 keys
.qsort (svalue::cmp_ptr_ptr
);
221 FOR_EACH_VEC_ELT (keys
, i
, sval
)
226 pp_string (pp
, ", ");
228 if (!flag_dump_noaddr
)
230 pp_pointer (pp
, sval
);
231 pp_string (pp
, ": ");
233 sval
->dump_to_pp (pp
, simple
);
235 entry_t e
= *const_cast <map_t
&> (m_map
).get (sval
);
236 pp_string (pp
, ": ");
237 e
.m_state
->dump_to_pp (pp
);
239 if (tree rep
= model
->get_representative_tree (sval
))
241 pp_string (pp
, " (");
242 dump_quoted_tree (pp
, rep
);
243 pp_character (pp
, ')');
247 pp_string (pp
, " (origin: ");
248 if (!flag_dump_noaddr
)
250 pp_pointer (pp
, e
.m_origin
);
251 pp_string (pp
, ": ");
253 e
.m_origin
->dump_to_pp (pp
, simple
);
255 if (tree rep
= model
->get_representative_tree (e
.m_origin
))
257 pp_string (pp
, " (");
258 dump_quoted_tree (pp
, rep
);
259 pp_character (pp
, ')');
270 /* Dump this object to stderr. */
273 sm_state_map::dump (bool simple
) const
276 pp_format_decoder (&pp
) = default_tree_printer
;
277 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
278 pp
.buffer
->stream
= stderr
;
279 print (NULL
, simple
, true, &pp
);
284 /* Return a new json::object of the form
285 {"global" : (optional) value for global state,
286 SVAL_DESC : value for state}. */
289 sm_state_map::to_json () const
291 json::object
*map_obj
= new json::object ();
293 if (m_global_state
!= m_sm
.get_start_state ())
294 map_obj
->set ("global", m_global_state
->to_json ());
295 for (map_t::iterator iter
= m_map
.begin ();
296 iter
!= m_map
.end ();
299 const svalue
*sval
= (*iter
).first
;
300 entry_t e
= (*iter
).second
;
302 label_text sval_desc
= sval
->get_desc ();
303 map_obj
->set (sval_desc
.m_buffer
, e
.m_state
->to_json ());
304 sval_desc
.maybe_free ();
306 /* This doesn't yet JSONify e.m_origin. */
311 /* Return true if no states have been set within this map
312 (all expressions are for the start state). */
315 sm_state_map::is_empty_p () const
317 return m_map
.elements () == 0 && m_global_state
== m_sm
.get_start_state ();
320 /* Generate a hash value for this sm_state_map. */
323 sm_state_map::hash () const
325 hashval_t result
= 0;
327 /* Accumulate the result by xoring a hash for each slot, so that the
328 result doesn't depend on the ordering of the slots in the map. */
330 for (map_t::iterator iter
= m_map
.begin ();
331 iter
!= m_map
.end ();
334 inchash::hash hstate
;
335 hstate
.add_ptr ((*iter
).first
);
336 entry_t e
= (*iter
).second
;
337 hstate
.add_int (e
.m_state
->get_id ());
338 hstate
.add_ptr (e
.m_origin
);
339 result
^= hstate
.end ();
341 result
^= m_global_state
->get_id ();
346 /* Equality operator for sm_state_map. */
349 sm_state_map::operator== (const sm_state_map
&other
) const
351 if (m_global_state
!= other
.m_global_state
)
354 if (m_map
.elements () != other
.m_map
.elements ())
357 for (map_t::iterator iter
= m_map
.begin ();
358 iter
!= m_map
.end ();
361 const svalue
*sval
= (*iter
).first
;
362 entry_t e
= (*iter
).second
;
363 entry_t
*other_slot
= const_cast <map_t
&> (other
.m_map
).get (sval
);
364 if (other_slot
== NULL
)
366 if (e
!= *other_slot
)
370 gcc_checking_assert (hash () == other
.hash ());
375 /* Get the state of SVAL within this object.
376 States default to the start state. */
378 state_machine::state_t
379 sm_state_map::get_state (const svalue
*sval
,
380 const extrinsic_state
&ext_state
) const
384 sval
= canonicalize_svalue (sval
, ext_state
);
387 = const_cast <map_t
&> (m_map
).get (sval
))
388 return slot
->m_state
;
390 /* SVAL has no explicit sm-state.
391 If this sm allows for state inheritance, then SVAL might have implicit
392 sm-state inherited via a parent.
393 For example INIT_VAL(foo.field) might inherit taintedness state from
395 if (m_sm
.inherited_state_p ())
396 if (region_model_manager
*mgr
= ext_state
.get_model_manager ())
398 if (const initial_svalue
*init_sval
= sval
->dyn_cast_initial_svalue ())
400 const region
*reg
= init_sval
->get_region ();
401 /* Try recursing upwards (up to the base region for the
403 if (!reg
->base_region_p ())
404 if (const region
*parent_reg
= reg
->get_parent_region ())
406 const svalue
*parent_init_sval
407 = mgr
->get_or_create_initial_value (parent_reg
);
408 state_machine::state_t parent_state
409 = get_state (parent_init_sval
, ext_state
);
414 else if (const sub_svalue
*sub_sval
= sval
->dyn_cast_sub_svalue ())
416 const svalue
*parent_sval
= sub_sval
->get_parent ();
417 if (state_machine::state_t parent_state
418 = get_state (parent_sval
, ext_state
))
423 return m_sm
.get_default_state (sval
);
426 /* Get the "origin" svalue for any state of SVAL. */
429 sm_state_map::get_origin (const svalue
*sval
,
430 const extrinsic_state
&ext_state
) const
434 sval
= canonicalize_svalue (sval
, ext_state
);
437 = const_cast <map_t
&> (m_map
).get (sval
);
439 return slot
->m_origin
;
444 /* Set the state of SID within MODEL to STATE, recording that
445 the state came from ORIGIN. */
448 sm_state_map::set_state (region_model
*model
,
450 state_machine::state_t state
,
451 const svalue
*origin
,
452 const extrinsic_state
&ext_state
)
457 /* Reject attempts to set state on UNKNOWN/POISONED. */
458 if (!sval
->can_have_associated_state_p ())
461 equiv_class
&ec
= model
->get_constraints ()->get_equiv_class (sval
);
462 if (!set_state (ec
, state
, origin
, ext_state
))
466 /* Set the state of EC to STATE, recording that the state came from
468 Return true if any states of svalue_ids within EC changed. */
471 sm_state_map::set_state (const equiv_class
&ec
,
472 state_machine::state_t state
,
473 const svalue
*origin
,
474 const extrinsic_state
&ext_state
)
476 bool any_changed
= false;
477 for (const svalue
*sval
: ec
.m_vars
)
478 any_changed
|= impl_set_state (sval
, state
, origin
, ext_state
);
482 /* Set state of SVAL to STATE, bypassing equivalence classes.
483 Return true if the state changed. */
486 sm_state_map::impl_set_state (const svalue
*sval
,
487 state_machine::state_t state
,
488 const svalue
*origin
,
489 const extrinsic_state
&ext_state
)
491 sval
= canonicalize_svalue (sval
, ext_state
);
493 if (get_state (sval
, ext_state
) == state
)
496 gcc_assert (sval
->can_have_associated_state_p ());
498 /* Special-case state 0 as the default value. */
501 if (m_map
.get (sval
))
506 m_map
.put (sval
, entry_t (state
, origin
));
510 /* Set the "global" state within this state map to STATE. */
513 sm_state_map::set_global_state (state_machine::state_t state
)
515 m_global_state
= state
;
518 /* Get the "global" state within this state map. */
520 state_machine::state_t
521 sm_state_map::get_global_state () const
523 return m_global_state
;
526 /* Purge any state for SVAL.
527 If !SM::can_purge_p, then report the state as leaking,
531 sm_state_map::on_svalue_leak (const svalue
*sval
,
532 impl_region_model_context
*ctxt
)
534 if (state_machine::state_t state
= get_state (sval
, ctxt
->m_ext_state
))
536 if (!m_sm
.can_purge_p (state
))
537 ctxt
->on_state_leak (m_sm
, sval
, state
);
542 /* Purge any state for svalues that aren't live with respect to LIVE_SVALUES
546 sm_state_map::on_liveness_change (const svalue_set
&live_svalues
,
547 const region_model
*model
,
548 impl_region_model_context
*ctxt
)
550 svalue_set svals_to_unset
;
551 uncertainty_t
*uncertainty
= ctxt
->get_uncertainty ();
553 auto_vec
<const svalue
*> leaked_svals (m_map
.elements ());
554 for (map_t::iterator iter
= m_map
.begin ();
555 iter
!= m_map
.end ();
558 const svalue
*iter_sval
= (*iter
).first
;
559 if (!iter_sval
->live_p (&live_svalues
, model
))
561 svals_to_unset
.add (iter_sval
);
562 entry_t e
= (*iter
).second
;
563 if (!m_sm
.can_purge_p (e
.m_state
))
564 leaked_svals
.quick_push (iter_sval
);
567 if (uncertainty
->unknown_sm_state_p (iter_sval
))
568 svals_to_unset
.add (iter_sval
);
571 leaked_svals
.qsort (svalue::cmp_ptr_ptr
);
575 FOR_EACH_VEC_ELT (leaked_svals
, i
, sval
)
577 entry_t e
= *m_map
.get (sval
);
578 ctxt
->on_state_leak (m_sm
, sval
, e
.m_state
);
581 for (svalue_set::iterator iter
= svals_to_unset
.begin ();
582 iter
!= svals_to_unset
.end (); ++iter
)
583 m_map
.remove (*iter
);
586 /* Purge state from SVAL (in response to a call to an unknown function). */
589 sm_state_map::on_unknown_change (const svalue
*sval
,
591 const extrinsic_state
&ext_state
)
593 svalue_set svals_to_unset
;
595 for (map_t::iterator iter
= m_map
.begin ();
596 iter
!= m_map
.end ();
599 const svalue
*key
= (*iter
).first
;
600 entry_t e
= (*iter
).second
;
601 /* We only want to purge state for some states when things
602 are mutable. For example, in sm-malloc.cc, an on-stack ptr
603 doesn't stop being stack-allocated when passed to an unknown fn. */
604 if (!m_sm
.reset_when_passed_to_unknown_fn_p (e
.m_state
, is_mutable
))
607 svals_to_unset
.add (key
);
608 /* If we have INIT_VAL(BASE_REG), then unset any INIT_VAL(REG)
609 for REG within BASE_REG. */
610 if (const initial_svalue
*init_sval
= sval
->dyn_cast_initial_svalue ())
611 if (const initial_svalue
*init_key
= key
->dyn_cast_initial_svalue ())
613 const region
*changed_reg
= init_sval
->get_region ();
614 const region
*changed_key
= init_key
->get_region ();
615 if (changed_key
->get_base_region () == changed_reg
)
616 svals_to_unset
.add (key
);
620 for (svalue_set::iterator iter
= svals_to_unset
.begin ();
621 iter
!= svals_to_unset
.end (); ++iter
)
622 impl_set_state (*iter
, (state_machine::state_t
)0, NULL
, ext_state
);
625 /* Purge state for things involving SVAL.
626 For use when SVAL changes meaning, at the def_stmt on an SSA_NAME. */
629 sm_state_map::purge_state_involving (const svalue
*sval
,
630 const extrinsic_state
&ext_state
)
632 /* Currently svalue::involves_p requires this. */
633 if (!(sval
->get_kind () == SK_INITIAL
634 || sval
->get_kind () == SK_CONJURED
))
637 svalue_set svals_to_unset
;
639 for (map_t::iterator iter
= m_map
.begin ();
640 iter
!= m_map
.end ();
643 const svalue
*key
= (*iter
).first
;
644 entry_t e
= (*iter
).second
;
645 if (!m_sm
.can_purge_p (e
.m_state
))
647 if (key
->involves_p (sval
))
648 svals_to_unset
.add (key
);
651 for (svalue_set::iterator iter
= svals_to_unset
.begin ();
652 iter
!= svals_to_unset
.end (); ++iter
)
653 impl_set_state (*iter
, (state_machine::state_t
)0, NULL
, ext_state
);
656 /* Comparator for imposing an order on sm_state_map instances. */
659 sm_state_map::cmp (const sm_state_map
&smap_a
, const sm_state_map
&smap_b
)
661 if (int cmp_count
= smap_a
.elements () - smap_b
.elements ())
664 auto_vec
<const svalue
*> keys_a (smap_a
.elements ());
665 for (map_t::iterator iter
= smap_a
.begin ();
666 iter
!= smap_a
.end ();
668 keys_a
.quick_push ((*iter
).first
);
669 keys_a
.qsort (svalue::cmp_ptr_ptr
);
671 auto_vec
<const svalue
*> keys_b (smap_b
.elements ());
672 for (map_t::iterator iter
= smap_b
.begin ();
673 iter
!= smap_b
.end ();
675 keys_b
.quick_push ((*iter
).first
);
676 keys_b
.qsort (svalue::cmp_ptr_ptr
);
679 const svalue
*sval_a
;
680 FOR_EACH_VEC_ELT (keys_a
, i
, sval_a
)
682 const svalue
*sval_b
= keys_b
[i
];
683 if (int cmp_sval
= svalue::cmp_ptr (sval_a
, sval_b
))
685 const entry_t
*e_a
= const_cast <map_t
&> (smap_a
.m_map
).get (sval_a
);
686 const entry_t
*e_b
= const_cast <map_t
&> (smap_b
.m_map
).get (sval_b
);
687 if (int cmp_entry
= entry_t::cmp (*e_a
, *e_b
))
694 /* Canonicalize SVAL before getting/setting it within the map.
695 Convert all NULL pointers to (void *) to avoid state explosions
696 involving all of the various (foo *)NULL vs (bar *)NULL. */
699 sm_state_map::canonicalize_svalue (const svalue
*sval
,
700 const extrinsic_state
&ext_state
)
702 region_model_manager
*mgr
= ext_state
.get_model_manager ();
703 if (mgr
&& sval
->get_type () && POINTER_TYPE_P (sval
->get_type ()))
704 if (tree cst
= sval
->maybe_get_constant ())
706 return mgr
->get_or_create_constant_svalue (null_pointer_node
);
711 /* class program_state. */
713 /* program_state's ctor. */
715 program_state::program_state (const extrinsic_state
&ext_state
)
716 : m_region_model (NULL
),
717 m_checker_states (ext_state
.get_num_checkers ()),
720 engine
*eng
= ext_state
.get_engine ();
721 region_model_manager
*mgr
= eng
->get_model_manager ();
722 m_region_model
= new region_model (mgr
);
723 const int num_states
= ext_state
.get_num_checkers ();
724 for (int i
= 0; i
< num_states
; i
++)
726 sm_state_map
*sm
= new sm_state_map (ext_state
.get_sm (i
));
727 m_checker_states
.quick_push (sm
);
731 /* program_state's copy ctor. */
733 program_state::program_state (const program_state
&other
)
734 : m_region_model (new region_model (*other
.m_region_model
)),
735 m_checker_states (other
.m_checker_states
.length ()),
740 FOR_EACH_VEC_ELT (other
.m_checker_states
, i
, smap
)
741 m_checker_states
.quick_push (smap
->clone ());
744 /* program_state's assignment operator. */
747 program_state::operator= (const program_state
&other
)
749 delete m_region_model
;
750 m_region_model
= new region_model (*other
.m_region_model
);
754 FOR_EACH_VEC_ELT (m_checker_states
, i
, smap
)
756 m_checker_states
.truncate (0);
757 gcc_assert (m_checker_states
.space (other
.m_checker_states
.length ()));
759 FOR_EACH_VEC_ELT (other
.m_checker_states
, i
, smap
)
760 m_checker_states
.quick_push (smap
->clone ());
762 m_valid
= other
.m_valid
;
767 /* Move constructor for program_state (when building with C++11). */
768 program_state::program_state (program_state
&&other
)
769 : m_region_model (other
.m_region_model
),
770 m_checker_states (other
.m_checker_states
.length ())
772 other
.m_region_model
= NULL
;
776 FOR_EACH_VEC_ELT (other
.m_checker_states
, i
, smap
)
777 m_checker_states
.quick_push (smap
);
778 other
.m_checker_states
.truncate (0);
780 m_valid
= other
.m_valid
;
783 /* program_state's dtor. */
785 program_state::~program_state ()
787 delete m_region_model
;
790 /* Generate a hash value for this program_state. */
793 program_state::hash () const
795 hashval_t result
= m_region_model
->hash ();
799 FOR_EACH_VEC_ELT (m_checker_states
, i
, smap
)
800 result
^= smap
->hash ();
804 /* Equality operator for program_state.
805 All parts of the program_state (region model, checker states) must
806 equal their counterparts in OTHER for the two program_states to be
810 program_state::operator== (const program_state
&other
) const
812 if (!(*m_region_model
== *other
.m_region_model
))
817 FOR_EACH_VEC_ELT (m_checker_states
, i
, smap
)
818 if (!(*smap
== *other
.m_checker_states
[i
]))
821 gcc_checking_assert (hash () == other
.hash ());
826 /* Print a compact representation of this state to PP. */
829 program_state::print (const extrinsic_state
&ext_state
,
830 pretty_printer
*pp
) const
832 pp_printf (pp
, "rmodel: ");
833 m_region_model
->dump_to_pp (pp
, true, false);
838 FOR_EACH_VEC_ELT (m_checker_states
, i
, smap
)
840 if (!smap
->is_empty_p ())
842 pp_printf (pp
, "%s: ", ext_state
.get_name (i
));
843 smap
->print (m_region_model
, true, false, pp
);
849 pp_printf (pp
, "invalid state");
854 /* Dump a representation of this state to PP. */
857 program_state::dump_to_pp (const extrinsic_state
&ext_state
,
858 bool /*summarize*/, bool multiline
,
859 pretty_printer
*pp
) const
864 pp_printf (pp
, "rmodel:");
868 pp_string (pp
, " {");
869 m_region_model
->dump_to_pp (pp
, true, multiline
);
876 FOR_EACH_VEC_ELT (m_checker_states
, i
, smap
)
878 if (!smap
->is_empty_p ())
881 pp_string (pp
, " {");
882 pp_printf (pp
, "%s: ", ext_state
.get_name (i
));
885 smap
->print (m_region_model
, true, multiline
, pp
);
895 pp_printf (pp
, "invalid state");
903 /* Dump a representation of this state to OUTF. */
906 program_state::dump_to_file (const extrinsic_state
&ext_state
,
907 bool summarize
, bool multiline
,
911 pp_format_decoder (&pp
) = default_tree_printer
;
913 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
914 pp
.buffer
->stream
= outf
;
915 dump_to_pp (ext_state
, summarize
, multiline
, &pp
);
919 /* Dump a multiline representation of this state to stderr. */
922 program_state::dump (const extrinsic_state
&ext_state
,
923 bool summarize
) const
925 dump_to_file (ext_state
, summarize
, true, stderr
);
928 /* Return a new json::object of the form
929 {"store" : object for store,
930 "constraints" : object for constraint_manager,
931 "curr_frame" : (optional) str for current frame,
932 "checkers" : { STATE_NAME : object per sm_state_map },
933 "valid" : true/false}. */
936 program_state::to_json (const extrinsic_state
&ext_state
) const
938 json::object
*state_obj
= new json::object ();
940 state_obj
->set ("store", m_region_model
->get_store ()->to_json ());
941 state_obj
->set ("constraints",
942 m_region_model
->get_constraints ()->to_json ());
943 if (m_region_model
->get_current_frame ())
944 state_obj
->set ("curr_frame",
945 m_region_model
->get_current_frame ()->to_json ());
947 /* Provide m_checker_states as an object, using names as keys. */
949 json::object
*checkers_obj
= new json::object ();
953 FOR_EACH_VEC_ELT (m_checker_states
, i
, smap
)
954 if (!smap
->is_empty_p ())
955 checkers_obj
->set (ext_state
.get_name (i
), smap
->to_json ());
957 state_obj
->set ("checkers", checkers_obj
);
960 state_obj
->set ("valid", new json::literal (m_valid
));
965 /* Update this program_state to reflect a top-level call to FUN.
966 The params will have initial_svalues. */
969 program_state::push_frame (const extrinsic_state
&ext_state ATTRIBUTE_UNUSED
,
972 m_region_model
->push_frame (fun
, NULL
, NULL
);
975 /* Get the current function of this state. */
978 program_state::get_current_function () const
980 return m_region_model
->get_current_function ();
983 /* Determine if following edge SUCC from ENODE is valid within the graph EG
984 and update this state accordingly in-place.
986 Return true if the edge can be followed, or false otherwise.
988 Check for relevant conditionals and switch-values for conditionals
989 and switch statements, adding the relevant conditions to this state.
990 Push/pop frames for interprocedural edges and update params/returned
993 This is the "state" half of exploded_node::on_edge. */
996 program_state::on_edge (exploded_graph
&eg
,
997 exploded_node
*enode
,
998 const superedge
*succ
,
999 uncertainty_t
*uncertainty
)
1002 const program_point
&point
= enode
->get_point ();
1003 const gimple
*last_stmt
= point
.get_supernode ()->get_last_stmt ();
1005 /* For conditionals and switch statements, add the
1006 relevant conditions (for the specific edge) to new_state;
1007 skip edges for which the resulting constraints
1009 This also updates frame information for call/return superedges.
1010 Adding the relevant conditions for the edge could also trigger
1011 sm-state transitions (e.g. transitions due to ptrs becoming known
1012 to be NULL or non-NULL) */
1014 impl_region_model_context
ctxt (eg
, enode
,
1015 &enode
->get_state (),
1019 if (!m_region_model
->maybe_update_for_edge (*succ
,
1023 logger
* const logger
= eg
.get_logger ();
1025 logger
->log ("edge to SN: %i is impossible"
1026 " due to region_model constraints",
1027 succ
->m_dest
->m_index
);
1031 program_state::detect_leaks (enode
->get_state (), *this,
1032 NULL
, eg
.get_ext_state (),
1038 /* Update this program_state to reflect a call to function
1039 represented by CALL_STMT.
1040 currently used only when the call doesn't have a superedge representing
1041 the call ( like call via a function pointer ) */
1043 program_state::push_call (exploded_graph
&eg
,
1044 exploded_node
*enode
,
1045 const gcall
*call_stmt
,
1046 uncertainty_t
*uncertainty
)
1049 const program_point
&point
= enode
->get_point ();
1050 const gimple
*last_stmt
= point
.get_supernode ()->get_last_stmt ();
1052 impl_region_model_context
ctxt (eg
, enode
,
1053 &enode
->get_state (),
1058 m_region_model
->update_for_gcall (call_stmt
, &ctxt
);
1061 /* Update this program_state to reflect a return from function
1062 call to which is represented by CALL_STMT.
1063 currently used only when the call doesn't have a superedge representing
1066 program_state::returning_call (exploded_graph
&eg
,
1067 exploded_node
*enode
,
1068 const gcall
*call_stmt
,
1069 uncertainty_t
*uncertainty
)
1072 const program_point
&point
= enode
->get_point ();
1073 const gimple
*last_stmt
= point
.get_supernode ()->get_last_stmt ();
1075 impl_region_model_context
ctxt (eg
, enode
,
1076 &enode
->get_state (),
1081 m_region_model
->update_for_return_gcall (call_stmt
, &ctxt
);
1084 /* Generate a simpler version of THIS, discarding state that's no longer
1086 The idea is that we're more likely to be able to consolidate
1087 multiple (point, state) into single exploded_nodes if we discard
1088 irrelevant state (e.g. at the end of functions). */
1091 program_state::prune_for_point (exploded_graph
&eg
,
1092 const program_point
&point
,
1093 exploded_node
*enode_for_diag
,
1094 uncertainty_t
*uncertainty
) const
1096 logger
* const logger
= eg
.get_logger ();
1099 function
*fun
= point
.get_function ();
1103 program_state
new_state (*this);
1105 const state_purge_map
*pm
= eg
.get_purge_map ();
1108 unsigned num_ssas_purged
= 0;
1109 auto_vec
<const decl_region
*> ssa_name_regs
;
1110 new_state
.m_region_model
->get_ssa_name_regions_for_current_frame
1112 ssa_name_regs
.qsort (region::cmp_ptr_ptr
);
1114 const decl_region
*reg
;
1115 FOR_EACH_VEC_ELT (ssa_name_regs
, i
, reg
)
1117 tree ssa_name
= reg
->get_decl ();
1118 const state_purge_per_ssa_name
&per_ssa
1119 = pm
->get_data_for_ssa_name (ssa_name
);
1120 if (!per_ssa
.needed_at_point_p (point
.get_function_point ()))
1122 /* Don't purge bindings of SSA names to svalues
1123 that have unpurgable sm-state, so that leaks are
1124 reported at the end of the function, rather than
1125 at the last place that such an SSA name is referred to.
1127 But do purge them for temporaries (when SSA_NAME_VAR is
1128 NULL), so that we report for cases where a leak happens when
1129 a variable is overwritten with another value, so that the leak
1130 is reported at the point of overwrite, rather than having
1131 temporaries keep the value reachable until the frame is
1134 = new_state
.m_region_model
->get_store_value (reg
, NULL
);
1135 if (!new_state
.can_purge_p (eg
.get_ext_state (), sval
)
1136 && SSA_NAME_VAR (ssa_name
))
1138 /* (currently only state maps can keep things
1141 logger
->log ("not purging binding for %qE"
1142 " (used by state map)", ssa_name
);
1146 new_state
.m_region_model
->purge_region (reg
);
1151 if (num_ssas_purged
> 0)
1154 logger
->log ("num_ssas_purged: %i", num_ssas_purged
);
1155 impl_region_model_context
ctxt (eg
, enode_for_diag
,
1160 detect_leaks (*this, new_state
, NULL
, eg
.get_ext_state (), &ctxt
);
1164 new_state
.m_region_model
->canonicalize ();
1169 /* Get a representative tree to use for describing SVAL. */
1172 program_state::get_representative_tree (const svalue
*sval
) const
1174 gcc_assert (m_region_model
);
1175 return m_region_model
->get_representative_tree (sval
);
1178 /* Attempt to merge this state with OTHER, both at POINT.
1179 Write the result to *OUT.
1180 If the states were merged successfully, return true. */
1183 program_state::can_merge_with_p (const program_state
&other
,
1184 const program_point
&point
,
1185 program_state
*out
) const
1188 gcc_assert (m_region_model
);
1190 /* Early reject if there are sm-differences between the states. */
1193 FOR_EACH_VEC_ELT (out
->m_checker_states
, i
, smap
)
1194 if (*m_checker_states
[i
] != *other
.m_checker_states
[i
])
1197 /* Attempt to merge the region_models. */
1198 if (!m_region_model
->can_merge_with_p (*other
.m_region_model
,
1200 out
->m_region_model
))
1203 /* Copy m_checker_states to OUT. */
1204 FOR_EACH_VEC_ELT (out
->m_checker_states
, i
, smap
)
1207 out
->m_checker_states
[i
] = m_checker_states
[i
]->clone ();
1210 out
->m_region_model
->canonicalize ();
1215 /* Assert that this object is valid. */
1218 program_state::validate (const extrinsic_state
&ext_state
) const
1220 /* Skip this in a release build. */
1225 gcc_assert (m_checker_states
.length () == ext_state
.get_num_checkers ());
1226 m_region_model
->validate ();
1230 log_set_of_svalues (logger
*logger
, const char *name
,
1231 const svalue_set
&set
)
1234 logger
->inc_indent ();
1235 auto_vec
<const svalue
*> sval_vecs (set
.elements ());
1236 for (svalue_set::iterator iter
= set
.begin ();
1237 iter
!= set
.end (); ++iter
)
1238 sval_vecs
.quick_push (*iter
);
1239 sval_vecs
.qsort (svalue::cmp_ptr_ptr
);
1242 FOR_EACH_VEC_ELT (sval_vecs
, i
, sval
)
1244 logger
->start_log_line ();
1245 pretty_printer
*pp
= logger
->get_printer ();
1246 if (!flag_dump_noaddr
)
1248 pp_pointer (pp
, sval
);
1249 pp_string (pp
, ": ");
1251 sval
->dump_to_pp (pp
, false);
1252 logger
->end_log_line ();
1254 logger
->dec_indent ();
1257 /* Compare the sets of svalues reachable from each of SRC_STATE and DEST_STATE.
1258 For all svalues that are reachable in SRC_STATE and are not live in
1259 DEST_STATE (whether explicitly reachable in DEST_STATE, or implicitly live
1260 based on the former set), call CTXT->on_svalue_leak for them.
1262 Call on_liveness_change on both the CTXT and on the DEST_STATE's
1263 constraint_manager, purging dead svalues from sm-state and from
1264 constraints, respectively.
1266 This function should be called at each fine-grained state change, not
1267 just at exploded edges. */
1270 program_state::detect_leaks (const program_state
&src_state
,
1271 const program_state
&dest_state
,
1272 const svalue
*extra_sval
,
1273 const extrinsic_state
&ext_state
,
1274 region_model_context
*ctxt
)
1276 logger
*logger
= ext_state
.get_logger ();
1278 const uncertainty_t
*uncertainty
= ctxt
->get_uncertainty ();
1281 pretty_printer
*pp
= logger
->get_printer ();
1282 logger
->start_log_line ();
1283 pp_string (pp
, "src_state: ");
1284 src_state
.dump_to_pp (ext_state
, true, false, pp
);
1285 logger
->end_log_line ();
1286 logger
->start_log_line ();
1287 pp_string (pp
, "dest_state: ");
1288 dest_state
.dump_to_pp (ext_state
, true, false, pp
);
1289 logger
->end_log_line ();
1292 logger
->start_log_line ();
1293 pp_string (pp
, "extra_sval: ");
1294 extra_sval
->dump_to_pp (pp
, true);
1295 logger
->end_log_line ();
1299 logger
->start_log_line ();
1300 pp_string (pp
, "uncertainty: ");
1301 uncertainty
->dump_to_pp (pp
, true);
1302 logger
->end_log_line ();
1306 /* Get svalues reachable from each of src_state and dest_state.
1307 Get svalues *known* to be reachable in src_state.
1308 Pass in uncertainty for dest_state so that we additionally get svalues that
1309 *might* still be reachable in dst_state. */
1310 svalue_set known_src_svalues
;
1311 src_state
.m_region_model
->get_reachable_svalues (&known_src_svalues
,
1313 svalue_set maybe_dest_svalues
;
1314 dest_state
.m_region_model
->get_reachable_svalues (&maybe_dest_svalues
,
1315 extra_sval
, uncertainty
);
1319 log_set_of_svalues (logger
, "src_state known reachable svalues:",
1321 log_set_of_svalues (logger
, "dest_state maybe reachable svalues:",
1322 maybe_dest_svalues
);
1325 auto_vec
<const svalue
*> dead_svals (known_src_svalues
.elements ());
1326 for (svalue_set::iterator iter
= known_src_svalues
.begin ();
1327 iter
!= known_src_svalues
.end (); ++iter
)
1329 const svalue
*sval
= (*iter
);
1330 /* For each sval reachable from SRC_STATE, determine if it is
1331 live in DEST_STATE: either explicitly reachable, implicitly
1332 live based on the set of explicitly reachable svalues,
1333 or possibly reachable as recorded in uncertainty.
1334 Record those that have ceased to be live i.e. were known
1335 to be live, and are now not known to be even possibly-live. */
1336 if (!sval
->live_p (&maybe_dest_svalues
, dest_state
.m_region_model
))
1337 dead_svals
.quick_push (sval
);
1340 /* Call CTXT->on_svalue_leak on all svals in SRC_STATE that have ceased
1341 to be live, sorting them first to ensure deterministic behavior. */
1342 dead_svals
.qsort (svalue::cmp_ptr_ptr
);
1345 FOR_EACH_VEC_ELT (dead_svals
, i
, sval
)
1346 ctxt
->on_svalue_leak (sval
);
1348 /* Purge dead svals from sm-state. */
1349 ctxt
->on_liveness_change (maybe_dest_svalues
,
1350 dest_state
.m_region_model
);
1352 /* Purge dead svals from constraints. */
1353 dest_state
.m_region_model
->get_constraints ()->on_liveness_change
1354 (maybe_dest_svalues
, dest_state
.m_region_model
);
1356 /* Purge dead heap-allocated regions from dynamic extents. */
1357 for (const svalue
*sval
: dead_svals
)
1358 if (const region
*reg
= sval
->maybe_get_region ())
1359 if (reg
->get_kind () == RK_HEAP_ALLOCATED
)
1360 dest_state
.m_region_model
->unset_dynamic_extents (reg
);
1363 /* Handle calls to "__analyzer_dump_state". */
1366 program_state::impl_call_analyzer_dump_state (const gcall
*call
,
1367 const extrinsic_state
&ext_state
,
1368 region_model_context
*ctxt
)
1370 call_details
cd (call
, m_region_model
, ctxt
);
1371 const char *sm_name
= cd
.get_arg_string_literal (0);
1374 error_at (call
->location
, "cannot determine state machine");
1378 if (!ext_state
.get_sm_idx_by_name (sm_name
, &sm_idx
))
1380 error_at (call
->location
, "unrecognized state machine %qs", sm_name
);
1383 const sm_state_map
*smap
= m_checker_states
[sm_idx
];
1385 const svalue
*sval
= cd
.get_arg_svalue (1);
1387 state_machine::state_t state
= smap
->get_state (sval
, ext_state
);
1388 warning_at (call
->location
, 0, "state: %qs", state
->get_name ());
1393 namespace selftest
{
1395 /* Tests for sm_state_map. */
1398 test_sm_state_map ()
1400 tree x
= build_global_decl ("x", integer_type_node
);
1401 tree y
= build_global_decl ("y", integer_type_node
);
1402 tree z
= build_global_decl ("z", integer_type_node
);
1404 state_machine
*sm
= make_malloc_state_machine (NULL
);
1405 auto_delete_vec
<state_machine
> checkers
;
1406 checkers
.safe_push (sm
);
1408 extrinsic_state
ext_state (checkers
, &eng
);
1409 state_machine::state_t start
= sm
->get_start_state ();
1411 /* Test setting states on svalue_id instances directly. */
1413 const state_machine::state
test_state_42 ("test state 42", 42);
1414 const state_machine::state_t TEST_STATE_42
= &test_state_42
;
1415 region_model_manager mgr
;
1416 region_model
model (&mgr
);
1417 const svalue
*x_sval
= model
.get_rvalue (x
, NULL
);
1418 const svalue
*y_sval
= model
.get_rvalue (y
, NULL
);
1419 const svalue
*z_sval
= model
.get_rvalue (z
, NULL
);
1421 sm_state_map
map (*sm
);
1422 ASSERT_TRUE (map
.is_empty_p ());
1423 ASSERT_EQ (map
.get_state (x_sval
, ext_state
), start
);
1425 map
.impl_set_state (x_sval
, TEST_STATE_42
, z_sval
, ext_state
);
1426 ASSERT_EQ (map
.get_state (x_sval
, ext_state
), TEST_STATE_42
);
1427 ASSERT_EQ (map
.get_origin (x_sval
, ext_state
), z_sval
);
1428 ASSERT_EQ (map
.get_state (y_sval
, ext_state
), start
);
1429 ASSERT_FALSE (map
.is_empty_p ());
1431 map
.impl_set_state (y_sval
, 0, z_sval
, ext_state
);
1432 ASSERT_EQ (map
.get_state (y_sval
, ext_state
), start
);
1434 map
.impl_set_state (x_sval
, 0, z_sval
, ext_state
);
1435 ASSERT_EQ (map
.get_state (x_sval
, ext_state
), start
);
1436 ASSERT_TRUE (map
.is_empty_p ());
1439 const state_machine::state
test_state_5 ("test state 5", 5);
1440 const state_machine::state_t TEST_STATE_5
= &test_state_5
;
1442 /* Test setting states via equivalence classes. */
1444 region_model_manager mgr
;
1445 region_model
model (&mgr
);
1446 const svalue
*x_sval
= model
.get_rvalue (x
, NULL
);
1447 const svalue
*y_sval
= model
.get_rvalue (y
, NULL
);
1448 const svalue
*z_sval
= model
.get_rvalue (z
, NULL
);
1450 sm_state_map
map (*sm
);
1451 ASSERT_TRUE (map
.is_empty_p ());
1452 ASSERT_EQ (map
.get_state (x_sval
, ext_state
), start
);
1453 ASSERT_EQ (map
.get_state (y_sval
, ext_state
), start
);
1455 model
.add_constraint (x
, EQ_EXPR
, y
, NULL
);
1457 /* Setting x to a state should also update y, as they
1458 are in the same equivalence class. */
1459 map
.set_state (&model
, x_sval
, TEST_STATE_5
, z_sval
, ext_state
);
1460 ASSERT_EQ (map
.get_state (x_sval
, ext_state
), TEST_STATE_5
);
1461 ASSERT_EQ (map
.get_state (y_sval
, ext_state
), TEST_STATE_5
);
1462 ASSERT_EQ (map
.get_origin (x_sval
, ext_state
), z_sval
);
1463 ASSERT_EQ (map
.get_origin (y_sval
, ext_state
), z_sval
);
1466 /* Test equality and hashing. */
1468 region_model_manager mgr
;
1469 region_model
model (&mgr
);
1470 const svalue
*y_sval
= model
.get_rvalue (y
, NULL
);
1471 const svalue
*z_sval
= model
.get_rvalue (z
, NULL
);
1473 sm_state_map
map0 (*sm
);
1474 sm_state_map
map1 (*sm
);
1475 sm_state_map
map2 (*sm
);
1477 ASSERT_EQ (map0
.hash (), map1
.hash ());
1478 ASSERT_EQ (map0
, map1
);
1480 map1
.impl_set_state (y_sval
, TEST_STATE_5
, z_sval
, ext_state
);
1481 ASSERT_NE (map0
.hash (), map1
.hash ());
1482 ASSERT_NE (map0
, map1
);
1484 /* Make the same change to map2. */
1485 map2
.impl_set_state (y_sval
, TEST_STATE_5
, z_sval
, ext_state
);
1486 ASSERT_EQ (map1
.hash (), map2
.hash ());
1487 ASSERT_EQ (map1
, map2
);
1490 /* Equality and hashing shouldn't depend on ordering. */
1492 const state_machine::state
test_state_2 ("test state 2", 2);
1493 const state_machine::state_t TEST_STATE_2
= &test_state_2
;
1494 const state_machine::state
test_state_3 ("test state 3", 3);
1495 const state_machine::state_t TEST_STATE_3
= &test_state_3
;
1496 sm_state_map
map0 (*sm
);
1497 sm_state_map
map1 (*sm
);
1498 sm_state_map
map2 (*sm
);
1500 ASSERT_EQ (map0
.hash (), map1
.hash ());
1501 ASSERT_EQ (map0
, map1
);
1503 region_model_manager mgr
;
1504 region_model
model (&mgr
);
1505 const svalue
*x_sval
= model
.get_rvalue (x
, NULL
);
1506 const svalue
*y_sval
= model
.get_rvalue (y
, NULL
);
1507 const svalue
*z_sval
= model
.get_rvalue (z
, NULL
);
1509 map1
.impl_set_state (x_sval
, TEST_STATE_2
, NULL
, ext_state
);
1510 map1
.impl_set_state (y_sval
, TEST_STATE_3
, NULL
, ext_state
);
1511 map1
.impl_set_state (z_sval
, TEST_STATE_2
, NULL
, ext_state
);
1513 map2
.impl_set_state (z_sval
, TEST_STATE_2
, NULL
, ext_state
);
1514 map2
.impl_set_state (y_sval
, TEST_STATE_3
, NULL
, ext_state
);
1515 map2
.impl_set_state (x_sval
, TEST_STATE_2
, NULL
, ext_state
);
1517 ASSERT_EQ (map1
.hash (), map2
.hash ());
1518 ASSERT_EQ (map1
, map2
);
1521 // TODO: coverage for purging
1524 /* Check program_state works as expected. */
1527 test_program_state_1 ()
1529 /* Create a program_state for a global ptr "p" that has
1530 malloc sm-state, pointing to a region on the heap. */
1531 tree p
= build_global_decl ("p", ptr_type_node
);
1533 state_machine
*sm
= make_malloc_state_machine (NULL
);
1534 const state_machine::state_t UNCHECKED_STATE
1535 = sm
->get_state_by_name ("unchecked");
1536 auto_delete_vec
<state_machine
> checkers
;
1537 checkers
.safe_push (sm
);
1540 extrinsic_state
ext_state (checkers
, &eng
);
1541 region_model_manager
*mgr
= eng
.get_model_manager ();
1542 program_state
s (ext_state
);
1543 region_model
*model
= s
.m_region_model
;
1544 const svalue
*size_in_bytes
1545 = mgr
->get_or_create_unknown_svalue (size_type_node
);
1546 const region
*new_reg
= model
->create_region_for_heap_alloc (size_in_bytes
);
1547 const svalue
*ptr_sval
= mgr
->get_ptr_svalue (ptr_type_node
, new_reg
);
1548 model
->set_value (model
->get_lvalue (p
, NULL
),
1550 sm_state_map
*smap
= s
.m_checker_states
[0];
1552 smap
->impl_set_state (ptr_sval
, UNCHECKED_STATE
, NULL
, ext_state
);
1553 ASSERT_EQ (smap
->get_state (ptr_sval
, ext_state
), UNCHECKED_STATE
);
1556 /* Check that program_state works for string literals. */
1559 test_program_state_2 ()
1561 /* Create a program_state for a global ptr "p" that points to
1562 a string constant. */
1563 tree p
= build_global_decl ("p", ptr_type_node
);
1565 tree string_cst_ptr
= build_string_literal (4, "foo");
1567 auto_delete_vec
<state_machine
> checkers
;
1569 extrinsic_state
ext_state (checkers
, &eng
);
1571 program_state
s (ext_state
);
1572 region_model
*model
= s
.m_region_model
;
1573 const region
*p_reg
= model
->get_lvalue (p
, NULL
);
1574 const svalue
*str_sval
= model
->get_rvalue (string_cst_ptr
, NULL
);
1575 model
->set_value (p_reg
, str_sval
, NULL
);
1578 /* Verify that program_states with identical sm-state can be merged,
1579 and that the merged program_state preserves the sm-state. */
1582 test_program_state_merging ()
1584 /* Create a program_state for a global ptr "p" that has
1585 malloc sm-state, pointing to a region on the heap. */
1586 tree p
= build_global_decl ("p", ptr_type_node
);
1588 program_point
point (program_point::origin ());
1589 auto_delete_vec
<state_machine
> checkers
;
1590 checkers
.safe_push (make_malloc_state_machine (NULL
));
1592 extrinsic_state
ext_state (checkers
, &eng
);
1593 region_model_manager
*mgr
= eng
.get_model_manager ();
1595 program_state
s0 (ext_state
);
1596 uncertainty_t uncertainty
;
1597 impl_region_model_context
ctxt (&s0
, ext_state
, &uncertainty
);
1599 region_model
*model0
= s0
.m_region_model
;
1600 const svalue
*size_in_bytes
1601 = mgr
->get_or_create_unknown_svalue (size_type_node
);
1602 const region
*new_reg
= model0
->create_region_for_heap_alloc (size_in_bytes
);
1603 const svalue
*ptr_sval
= mgr
->get_ptr_svalue (ptr_type_node
, new_reg
);
1604 model0
->set_value (model0
->get_lvalue (p
, &ctxt
),
1606 sm_state_map
*smap
= s0
.m_checker_states
[0];
1607 const state_machine::state
test_state ("test state", 0);
1608 const state_machine::state_t TEST_STATE
= &test_state
;
1609 smap
->impl_set_state (ptr_sval
, TEST_STATE
, NULL
, ext_state
);
1610 ASSERT_EQ (smap
->get_state (ptr_sval
, ext_state
), TEST_STATE
);
1612 model0
->canonicalize ();
1614 /* Verify that canonicalization preserves sm-state. */
1615 ASSERT_EQ (smap
->get_state (model0
->get_rvalue (p
, NULL
), ext_state
),
1618 /* Make a copy of the program_state. */
1619 program_state
s1 (s0
);
1622 /* We have two identical states with "p" pointing to a heap region
1623 with the given sm-state.
1624 They ought to be mergeable, preserving the sm-state. */
1625 program_state
merged (ext_state
);
1626 ASSERT_TRUE (s0
.can_merge_with_p (s1
, point
, &merged
));
1627 merged
.validate (ext_state
);
1629 /* Verify that the merged state has the sm-state for "p". */
1630 region_model
*merged_model
= merged
.m_region_model
;
1631 sm_state_map
*merged_smap
= merged
.m_checker_states
[0];
1632 ASSERT_EQ (merged_smap
->get_state (merged_model
->get_rvalue (p
, NULL
),
1636 /* Try canonicalizing. */
1637 merged
.m_region_model
->canonicalize ();
1638 merged
.validate (ext_state
);
1640 /* Verify that the merged state still has the sm-state for "p". */
1641 ASSERT_EQ (merged_smap
->get_state (merged_model
->get_rvalue (p
, NULL
),
1645 /* After canonicalization, we ought to have equality with the inputs. */
1646 ASSERT_EQ (s0
, merged
);
1649 /* Verify that program_states with different global-state in an sm-state
1653 test_program_state_merging_2 ()
1655 program_point
point (program_point::origin ());
1656 auto_delete_vec
<state_machine
> checkers
;
1657 checkers
.safe_push (make_signal_state_machine (NULL
));
1659 extrinsic_state
ext_state (checkers
, &eng
);
1661 const state_machine::state
test_state_0 ("test state 0", 0);
1662 const state_machine::state
test_state_1 ("test state 1", 1);
1663 const state_machine::state_t TEST_STATE_0
= &test_state_0
;
1664 const state_machine::state_t TEST_STATE_1
= &test_state_1
;
1666 program_state
s0 (ext_state
);
1668 sm_state_map
*smap0
= s0
.m_checker_states
[0];
1669 smap0
->set_global_state (TEST_STATE_0
);
1670 ASSERT_EQ (smap0
->get_global_state (), TEST_STATE_0
);
1673 program_state
s1 (ext_state
);
1675 sm_state_map
*smap1
= s1
.m_checker_states
[0];
1676 smap1
->set_global_state (TEST_STATE_1
);
1677 ASSERT_EQ (smap1
->get_global_state (), TEST_STATE_1
);
1682 /* They ought to not be mergeable. */
1683 program_state
merged (ext_state
);
1684 ASSERT_FALSE (s0
.can_merge_with_p (s1
, point
, &merged
));
1687 /* Run all of the selftests within this file. */
1690 analyzer_program_state_cc_tests ()
1692 test_sm_state_map ();
1693 test_program_state_1 ();
1694 test_program_state_2 ();
1695 test_program_state_merging ();
1696 test_program_state_merging_2 ();
1699 } // namespace selftest
1701 #endif /* CHECKING_P */
1705 #endif /* #if ENABLE_ANALYZER */