1 /* Classes for representing the state of interest at a given path of analysis.
2 Copyright (C) 2019-2022 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"
27 #include "analyzer/analyzer.h"
28 #include "analyzer/analyzer-logging.h"
29 #include "analyzer/sm.h"
32 #include "ordered-hash-map.h"
34 #include "analyzer/call-string.h"
35 #include "analyzer/program-point.h"
36 #include "analyzer/store.h"
37 #include "analyzer/region-model.h"
38 #include "analyzer/program-state.h"
39 #include "analyzer/constraint-manager.h"
40 #include "diagnostic-event-id.h"
41 #include "analyzer/pending-diagnostic.h"
42 #include "analyzer/diagnostic-manager.h"
44 #include "basic-block.h"
46 #include "gimple-iterator.h"
49 #include "analyzer/supergraph.h"
50 #include "analyzer/program-state.h"
51 #include "analyzer/exploded-graph.h"
52 #include "analyzer/state-purge.h"
53 #include "analyzer/call-summary.h"
54 #include "analyzer/analyzer-selftests.h"
60 /* class extrinsic_state. */
62 /* Dump a multiline representation of this state to PP. */
65 extrinsic_state::dump_to_pp (pretty_printer
*pp
) const
67 pp_printf (pp
, "extrinsic_state: %i checker(s)\n", get_num_checkers ());
69 state_machine
*checker
;
70 FOR_EACH_VEC_ELT (m_checkers
, i
, checker
)
72 pp_printf (pp
, "m_checkers[%i]: %qs\n", i
, checker
->get_name ());
73 checker
->dump_to_pp (pp
);
77 /* Dump a multiline representation of this state to OUTF. */
80 extrinsic_state::dump_to_file (FILE *outf
) const
84 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
85 pp
.buffer
->stream
= outf
;
90 /* Dump a multiline representation of this state to stderr. */
93 extrinsic_state::dump () const
95 dump_to_file (stderr
);
98 /* Return a new json::object of the form
99 {"checkers" : array of objects, one for each state_machine}. */
102 extrinsic_state::to_json () const
104 json::object
*ext_state_obj
= new json::object ();
107 json::array
*checkers_arr
= new json::array ();
110 FOR_EACH_VEC_ELT (m_checkers
, i
, sm
)
111 checkers_arr
->append (sm
->to_json ());
112 ext_state_obj
->set ("checkers", checkers_arr
);
115 return ext_state_obj
;
118 /* Get the region_model_manager for this extrinsic_state. */
120 region_model_manager
*
121 extrinsic_state::get_model_manager () const
124 return m_engine
->get_model_manager ();
126 return NULL
; /* for selftests. */
129 /* Try to find a state machine named NAME.
130 If found, return true and write its index to *OUT.
131 Otherwise return false. */
134 extrinsic_state::get_sm_idx_by_name (const char *name
, unsigned *out
) const
138 FOR_EACH_VEC_ELT (m_checkers
, i
, sm
)
139 if (0 == strcmp (name
, sm
->get_name ()))
146 /* NAME not found. */
150 /* struct sm_state_map::entry_t. */
153 sm_state_map::entry_t::cmp (const entry_t
&entry_a
, const entry_t
&entry_b
)
155 gcc_assert (entry_a
.m_state
);
156 gcc_assert (entry_b
.m_state
);
157 if (int cmp_state
= ((int)entry_a
.m_state
->get_id ()
158 - (int)entry_b
.m_state
->get_id ()))
160 if (entry_a
.m_origin
&& entry_b
.m_origin
)
161 return svalue::cmp_ptr (entry_a
.m_origin
, entry_b
.m_origin
);
162 if (entry_a
.m_origin
)
164 if (entry_b
.m_origin
)
169 /* class sm_state_map. */
171 /* sm_state_map's ctor. */
173 sm_state_map::sm_state_map (const state_machine
&sm
)
174 : m_sm (sm
), m_map (), m_global_state (sm
.get_start_state ())
178 /* Clone the sm_state_map. */
181 sm_state_map::clone () const
183 return new sm_state_map (*this);
186 /* Print this sm_state_map to PP.
187 If MODEL is non-NULL, print representative tree values where
191 sm_state_map::print (const region_model
*model
,
192 bool simple
, bool multiline
,
193 pretty_printer
*pp
) const
198 if (m_global_state
!= m_sm
.get_start_state ())
202 pp_string (pp
, "global: ");
203 m_global_state
->dump_to_pp (pp
);
208 auto_vec
<const svalue
*> keys (m_map
.elements ());
209 for (map_t::iterator iter
= m_map
.begin ();
210 iter
!= m_map
.end ();
212 keys
.quick_push ((*iter
).first
);
213 keys
.qsort (svalue::cmp_ptr_ptr
);
216 FOR_EACH_VEC_ELT (keys
, i
, sval
)
221 pp_string (pp
, ", ");
223 if (!flag_dump_noaddr
)
225 pp_pointer (pp
, sval
);
226 pp_string (pp
, ": ");
228 sval
->dump_to_pp (pp
, simple
);
230 entry_t e
= *const_cast <map_t
&> (m_map
).get (sval
);
231 pp_string (pp
, ": ");
232 e
.m_state
->dump_to_pp (pp
);
234 if (tree rep
= model
->get_representative_tree (sval
))
236 pp_string (pp
, " (");
237 dump_quoted_tree (pp
, rep
);
238 pp_character (pp
, ')');
242 pp_string (pp
, " (origin: ");
243 if (!flag_dump_noaddr
)
245 pp_pointer (pp
, e
.m_origin
);
246 pp_string (pp
, ": ");
248 e
.m_origin
->dump_to_pp (pp
, simple
);
250 if (tree rep
= model
->get_representative_tree (e
.m_origin
))
252 pp_string (pp
, " (");
253 dump_quoted_tree (pp
, rep
);
254 pp_character (pp
, ')');
265 /* Dump this object to stderr. */
268 sm_state_map::dump (bool simple
) const
271 pp_format_decoder (&pp
) = default_tree_printer
;
272 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
273 pp
.buffer
->stream
= stderr
;
274 print (NULL
, simple
, true, &pp
);
279 /* Return a new json::object of the form
280 {"global" : (optional) value for global state,
281 SVAL_DESC : value for state}. */
284 sm_state_map::to_json () const
286 json::object
*map_obj
= new json::object ();
288 if (m_global_state
!= m_sm
.get_start_state ())
289 map_obj
->set ("global", m_global_state
->to_json ());
290 for (map_t::iterator iter
= m_map
.begin ();
291 iter
!= m_map
.end ();
294 const svalue
*sval
= (*iter
).first
;
295 entry_t e
= (*iter
).second
;
297 label_text sval_desc
= sval
->get_desc ();
298 map_obj
->set (sval_desc
.get (), e
.m_state
->to_json ());
300 /* This doesn't yet JSONify e.m_origin. */
305 /* Return true if no states have been set within this map
306 (all expressions are for the start state). */
309 sm_state_map::is_empty_p () const
311 return m_map
.elements () == 0 && m_global_state
== m_sm
.get_start_state ();
314 /* Generate a hash value for this sm_state_map. */
317 sm_state_map::hash () const
319 hashval_t result
= 0;
321 /* Accumulate the result by xoring a hash for each slot, so that the
322 result doesn't depend on the ordering of the slots in the map. */
324 for (map_t::iterator iter
= m_map
.begin ();
325 iter
!= m_map
.end ();
328 inchash::hash hstate
;
329 hstate
.add_ptr ((*iter
).first
);
330 entry_t e
= (*iter
).second
;
331 hstate
.add_int (e
.m_state
->get_id ());
332 hstate
.add_ptr (e
.m_origin
);
333 result
^= hstate
.end ();
335 result
^= m_global_state
->get_id ();
340 /* Equality operator for sm_state_map. */
343 sm_state_map::operator== (const sm_state_map
&other
) const
345 if (m_global_state
!= other
.m_global_state
)
348 if (m_map
.elements () != other
.m_map
.elements ())
351 for (map_t::iterator iter
= m_map
.begin ();
352 iter
!= m_map
.end ();
355 const svalue
*sval
= (*iter
).first
;
356 entry_t e
= (*iter
).second
;
357 entry_t
*other_slot
= const_cast <map_t
&> (other
.m_map
).get (sval
);
358 if (other_slot
== NULL
)
360 if (e
!= *other_slot
)
364 gcc_checking_assert (hash () == other
.hash ());
369 /* Get the state of SVAL within this object.
370 States default to the start state. */
372 state_machine::state_t
373 sm_state_map::get_state (const svalue
*sval
,
374 const extrinsic_state
&ext_state
) const
378 sval
= canonicalize_svalue (sval
, ext_state
);
381 = const_cast <map_t
&> (m_map
).get (sval
))
382 return slot
->m_state
;
384 /* SVAL has no explicit sm-state.
385 If this sm allows for state inheritance, then SVAL might have implicit
386 sm-state inherited via a parent.
387 For example INIT_VAL(foo.field) might inherit taintedness state from
389 if (m_sm
.inherited_state_p ())
390 if (region_model_manager
*mgr
= ext_state
.get_model_manager ())
392 if (const initial_svalue
*init_sval
= sval
->dyn_cast_initial_svalue ())
394 const region
*reg
= init_sval
->get_region ();
395 /* Try recursing upwards (up to the base region for the
397 if (!reg
->base_region_p ())
398 if (const region
*parent_reg
= reg
->get_parent_region ())
400 const svalue
*parent_init_sval
401 = mgr
->get_or_create_initial_value (parent_reg
);
402 state_machine::state_t parent_state
403 = get_state (parent_init_sval
, ext_state
);
408 else if (const sub_svalue
*sub_sval
= sval
->dyn_cast_sub_svalue ())
410 const svalue
*parent_sval
= sub_sval
->get_parent ();
411 if (state_machine::state_t parent_state
412 = get_state (parent_sval
, ext_state
))
417 if (state_machine::state_t state
418 = m_sm
.alt_get_inherited_state (*this, sval
, ext_state
))
421 return m_sm
.get_default_state (sval
);
424 /* Get the "origin" svalue for any state of SVAL. */
427 sm_state_map::get_origin (const svalue
*sval
,
428 const extrinsic_state
&ext_state
) const
432 sval
= canonicalize_svalue (sval
, ext_state
);
435 = const_cast <map_t
&> (m_map
).get (sval
);
437 return slot
->m_origin
;
442 /* Set the state of SID within MODEL to STATE, recording that
443 the state came from ORIGIN. */
446 sm_state_map::set_state (region_model
*model
,
448 state_machine::state_t state
,
449 const svalue
*origin
,
450 const extrinsic_state
&ext_state
)
455 /* Reject attempts to set state on UNKNOWN/POISONED. */
456 if (!sval
->can_have_associated_state_p ())
459 equiv_class
&ec
= model
->get_constraints ()->get_equiv_class (sval
);
460 if (!set_state (ec
, state
, origin
, ext_state
))
464 /* Set the state of EC to STATE, recording that the state came from
466 Return true if any states of svalue_ids within EC changed. */
469 sm_state_map::set_state (const equiv_class
&ec
,
470 state_machine::state_t state
,
471 const svalue
*origin
,
472 const extrinsic_state
&ext_state
)
474 bool any_changed
= false;
475 for (const svalue
*sval
: ec
.m_vars
)
476 any_changed
|= impl_set_state (sval
, state
, origin
, ext_state
);
480 /* Set state of SVAL to STATE, bypassing equivalence classes.
481 Return true if the state changed. */
484 sm_state_map::impl_set_state (const svalue
*sval
,
485 state_machine::state_t state
,
486 const svalue
*origin
,
487 const extrinsic_state
&ext_state
)
489 sval
= canonicalize_svalue (sval
, ext_state
);
491 if (get_state (sval
, ext_state
) == state
)
494 gcc_assert (sval
->can_have_associated_state_p ());
496 if (m_sm
.inherited_state_p ())
498 if (const compound_svalue
*compound_sval
499 = sval
->dyn_cast_compound_svalue ())
500 for (auto iter
: *compound_sval
)
502 const svalue
*inner_sval
= iter
.second
;
503 if (inner_sval
->can_have_associated_state_p ())
504 impl_set_state (inner_sval
, state
, origin
, ext_state
);
508 /* Special-case state 0 as the default value. */
511 if (m_map
.get (sval
))
516 m_map
.put (sval
, entry_t (state
, origin
));
520 /* Set the "global" state within this state map to STATE. */
523 sm_state_map::set_global_state (state_machine::state_t state
)
525 m_global_state
= state
;
528 /* Get the "global" state within this state map. */
530 state_machine::state_t
531 sm_state_map::get_global_state () const
533 return m_global_state
;
536 /* Purge any state for SVAL.
537 If !SM::can_purge_p, then report the state as leaking,
541 sm_state_map::on_svalue_leak (const svalue
*sval
,
542 impl_region_model_context
*ctxt
)
544 if (state_machine::state_t state
= get_state (sval
, ctxt
->m_ext_state
))
546 if (!m_sm
.can_purge_p (state
))
547 ctxt
->on_state_leak (m_sm
, sval
, state
);
552 /* Purge any state for svalues that aren't live with respect to LIVE_SVALUES
556 sm_state_map::on_liveness_change (const svalue_set
&live_svalues
,
557 const region_model
*model
,
558 impl_region_model_context
*ctxt
)
560 svalue_set svals_to_unset
;
561 uncertainty_t
*uncertainty
= ctxt
->get_uncertainty ();
563 auto_vec
<const svalue
*> leaked_svals (m_map
.elements ());
564 for (map_t::iterator iter
= m_map
.begin ();
565 iter
!= m_map
.end ();
568 const svalue
*iter_sval
= (*iter
).first
;
569 if (!iter_sval
->live_p (&live_svalues
, model
))
571 svals_to_unset
.add (iter_sval
);
572 entry_t e
= (*iter
).second
;
573 if (!m_sm
.can_purge_p (e
.m_state
))
574 leaked_svals
.quick_push (iter_sval
);
577 if (uncertainty
->unknown_sm_state_p (iter_sval
))
578 svals_to_unset
.add (iter_sval
);
581 leaked_svals
.qsort (svalue::cmp_ptr_ptr
);
585 FOR_EACH_VEC_ELT (leaked_svals
, i
, sval
)
587 entry_t e
= *m_map
.get (sval
);
588 ctxt
->on_state_leak (m_sm
, sval
, e
.m_state
);
591 for (svalue_set::iterator iter
= svals_to_unset
.begin ();
592 iter
!= svals_to_unset
.end (); ++iter
)
593 m_map
.remove (*iter
);
596 /* Purge state from SVAL (in response to a call to an unknown function). */
599 sm_state_map::on_unknown_change (const svalue
*sval
,
601 const extrinsic_state
&ext_state
)
603 svalue_set svals_to_unset
;
605 for (map_t::iterator iter
= m_map
.begin ();
606 iter
!= m_map
.end ();
609 const svalue
*key
= (*iter
).first
;
610 entry_t e
= (*iter
).second
;
611 /* We only want to purge state for some states when things
612 are mutable. For example, in sm-malloc.cc, an on-stack ptr
613 doesn't stop being stack-allocated when passed to an unknown fn. */
614 if (!m_sm
.reset_when_passed_to_unknown_fn_p (e
.m_state
, is_mutable
))
617 svals_to_unset
.add (key
);
618 /* If we have INIT_VAL(BASE_REG), then unset any INIT_VAL(REG)
619 for REG within BASE_REG. */
620 if (const initial_svalue
*init_sval
= sval
->dyn_cast_initial_svalue ())
621 if (const initial_svalue
*init_key
= key
->dyn_cast_initial_svalue ())
623 const region
*changed_reg
= init_sval
->get_region ();
624 const region
*changed_key
= init_key
->get_region ();
625 if (changed_key
->get_base_region () == changed_reg
)
626 svals_to_unset
.add (key
);
630 for (svalue_set::iterator iter
= svals_to_unset
.begin ();
631 iter
!= svals_to_unset
.end (); ++iter
)
632 impl_set_state (*iter
, (state_machine::state_t
)0, NULL
, ext_state
);
635 /* Purge state for things involving SVAL.
636 For use when SVAL changes meaning, at the def_stmt on an SSA_NAME. */
639 sm_state_map::purge_state_involving (const svalue
*sval
,
640 const extrinsic_state
&ext_state
)
642 /* Currently svalue::involves_p requires this. */
643 if (!(sval
->get_kind () == SK_INITIAL
644 || sval
->get_kind () == SK_CONJURED
))
647 svalue_set svals_to_unset
;
649 for (map_t::iterator iter
= m_map
.begin ();
650 iter
!= m_map
.end ();
653 const svalue
*key
= (*iter
).first
;
654 entry_t e
= (*iter
).second
;
655 if (!m_sm
.can_purge_p (e
.m_state
))
657 if (key
->involves_p (sval
))
658 svals_to_unset
.add (key
);
661 for (svalue_set::iterator iter
= svals_to_unset
.begin ();
662 iter
!= svals_to_unset
.end (); ++iter
)
663 impl_set_state (*iter
, (state_machine::state_t
)0, NULL
, ext_state
);
666 /* Comparator for imposing an order on sm_state_map instances. */
669 sm_state_map::cmp (const sm_state_map
&smap_a
, const sm_state_map
&smap_b
)
671 if (int cmp_count
= smap_a
.elements () - smap_b
.elements ())
674 auto_vec
<const svalue
*> keys_a (smap_a
.elements ());
675 for (map_t::iterator iter
= smap_a
.begin ();
676 iter
!= smap_a
.end ();
678 keys_a
.quick_push ((*iter
).first
);
679 keys_a
.qsort (svalue::cmp_ptr_ptr
);
681 auto_vec
<const svalue
*> keys_b (smap_b
.elements ());
682 for (map_t::iterator iter
= smap_b
.begin ();
683 iter
!= smap_b
.end ();
685 keys_b
.quick_push ((*iter
).first
);
686 keys_b
.qsort (svalue::cmp_ptr_ptr
);
689 const svalue
*sval_a
;
690 FOR_EACH_VEC_ELT (keys_a
, i
, sval_a
)
692 const svalue
*sval_b
= keys_b
[i
];
693 if (int cmp_sval
= svalue::cmp_ptr (sval_a
, sval_b
))
695 const entry_t
*e_a
= const_cast <map_t
&> (smap_a
.m_map
).get (sval_a
);
696 const entry_t
*e_b
= const_cast <map_t
&> (smap_b
.m_map
).get (sval_b
);
697 if (int cmp_entry
= entry_t::cmp (*e_a
, *e_b
))
704 /* Canonicalize SVAL before getting/setting it within the map.
705 Convert all NULL pointers to (void *) to avoid state explosions
706 involving all of the various (foo *)NULL vs (bar *)NULL. */
709 sm_state_map::canonicalize_svalue (const svalue
*sval
,
710 const extrinsic_state
&ext_state
)
712 region_model_manager
*mgr
= ext_state
.get_model_manager ();
713 if (mgr
&& sval
->get_type () && POINTER_TYPE_P (sval
->get_type ()))
714 if (tree cst
= sval
->maybe_get_constant ())
716 return mgr
->get_or_create_constant_svalue (null_pointer_node
);
721 /* class program_state. */
723 /* program_state's ctor. */
725 program_state::program_state (const extrinsic_state
&ext_state
)
726 : m_region_model (NULL
),
727 m_checker_states (ext_state
.get_num_checkers ()),
730 engine
*eng
= ext_state
.get_engine ();
731 region_model_manager
*mgr
= eng
->get_model_manager ();
732 m_region_model
= new region_model (mgr
);
733 const int num_states
= ext_state
.get_num_checkers ();
734 for (int i
= 0; i
< num_states
; i
++)
736 sm_state_map
*sm
= new sm_state_map (ext_state
.get_sm (i
));
737 m_checker_states
.quick_push (sm
);
741 /* Attempt to to use R to replay SUMMARY into this object.
742 Return true if it is possible. */
745 sm_state_map::replay_call_summary (call_summary_replay
&r
,
746 const sm_state_map
&summary
)
748 for (auto kv
: summary
.m_map
)
750 const svalue
*summary_sval
= kv
.first
;
751 const svalue
*caller_sval
= r
.convert_svalue_from_summary (summary_sval
);
754 const svalue
*summary_origin
= kv
.second
.m_origin
;
755 const svalue
*caller_origin
757 ? r
.convert_svalue_from_summary (summary_origin
)
759 // caller_origin can be NULL.
760 m_map
.put (caller_sval
, entry_t (kv
.second
.m_state
, caller_origin
));
762 m_global_state
= summary
.m_global_state
;
766 /* program_state's copy ctor. */
768 program_state::program_state (const program_state
&other
)
769 : m_region_model (new region_model (*other
.m_region_model
)),
770 m_checker_states (other
.m_checker_states
.length ()),
775 FOR_EACH_VEC_ELT (other
.m_checker_states
, i
, smap
)
776 m_checker_states
.quick_push (smap
->clone ());
779 /* program_state's assignment operator. */
782 program_state::operator= (const program_state
&other
)
784 delete m_region_model
;
785 m_region_model
= new region_model (*other
.m_region_model
);
789 FOR_EACH_VEC_ELT (m_checker_states
, i
, smap
)
791 m_checker_states
.truncate (0);
792 gcc_assert (m_checker_states
.space (other
.m_checker_states
.length ()));
794 FOR_EACH_VEC_ELT (other
.m_checker_states
, i
, smap
)
795 m_checker_states
.quick_push (smap
->clone ());
797 m_valid
= other
.m_valid
;
802 /* Move constructor for program_state (when building with C++11). */
803 program_state::program_state (program_state
&&other
)
804 : m_region_model (other
.m_region_model
),
805 m_checker_states (other
.m_checker_states
.length ())
807 other
.m_region_model
= NULL
;
811 FOR_EACH_VEC_ELT (other
.m_checker_states
, i
, smap
)
812 m_checker_states
.quick_push (smap
);
813 other
.m_checker_states
.truncate (0);
815 m_valid
= other
.m_valid
;
818 /* program_state's dtor. */
820 program_state::~program_state ()
822 delete m_region_model
;
825 /* Generate a hash value for this program_state. */
828 program_state::hash () const
830 hashval_t result
= m_region_model
->hash ();
834 FOR_EACH_VEC_ELT (m_checker_states
, i
, smap
)
835 result
^= smap
->hash ();
839 /* Equality operator for program_state.
840 All parts of the program_state (region model, checker states) must
841 equal their counterparts in OTHER for the two program_states to be
845 program_state::operator== (const program_state
&other
) const
847 if (!(*m_region_model
== *other
.m_region_model
))
852 FOR_EACH_VEC_ELT (m_checker_states
, i
, smap
)
853 if (!(*smap
== *other
.m_checker_states
[i
]))
856 gcc_checking_assert (hash () == other
.hash ());
861 /* Print a compact representation of this state to PP. */
864 program_state::print (const extrinsic_state
&ext_state
,
865 pretty_printer
*pp
) const
867 pp_printf (pp
, "rmodel: ");
868 m_region_model
->dump_to_pp (pp
, true, false);
873 FOR_EACH_VEC_ELT (m_checker_states
, i
, smap
)
875 if (!smap
->is_empty_p ())
877 pp_printf (pp
, "%s: ", ext_state
.get_name (i
));
878 smap
->print (m_region_model
, true, false, pp
);
884 pp_printf (pp
, "invalid state");
889 /* Dump a representation of this state to PP. */
892 program_state::dump_to_pp (const extrinsic_state
&ext_state
,
893 bool /*summarize*/, bool multiline
,
894 pretty_printer
*pp
) const
899 pp_printf (pp
, "rmodel:");
903 pp_string (pp
, " {");
904 m_region_model
->dump_to_pp (pp
, true, multiline
);
911 FOR_EACH_VEC_ELT (m_checker_states
, i
, smap
)
913 if (!smap
->is_empty_p ())
916 pp_string (pp
, " {");
917 pp_printf (pp
, "%s: ", ext_state
.get_name (i
));
920 smap
->print (m_region_model
, true, multiline
, pp
);
930 pp_printf (pp
, "invalid state");
938 /* Dump a representation of this state to OUTF. */
941 program_state::dump_to_file (const extrinsic_state
&ext_state
,
942 bool summarize
, bool multiline
,
946 pp_format_decoder (&pp
) = default_tree_printer
;
948 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
949 pp
.buffer
->stream
= outf
;
950 dump_to_pp (ext_state
, summarize
, multiline
, &pp
);
954 /* Dump a multiline representation of this state to stderr. */
957 program_state::dump (const extrinsic_state
&ext_state
,
958 bool summarize
) const
960 dump_to_file (ext_state
, summarize
, true, stderr
);
963 /* Return a new json::object of the form
964 {"store" : object for store,
965 "constraints" : object for constraint_manager,
966 "curr_frame" : (optional) str for current frame,
967 "checkers" : { STATE_NAME : object per sm_state_map },
968 "valid" : true/false}. */
971 program_state::to_json (const extrinsic_state
&ext_state
) const
973 json::object
*state_obj
= new json::object ();
975 state_obj
->set ("store", m_region_model
->get_store ()->to_json ());
976 state_obj
->set ("constraints",
977 m_region_model
->get_constraints ()->to_json ());
978 if (m_region_model
->get_current_frame ())
979 state_obj
->set ("curr_frame",
980 m_region_model
->get_current_frame ()->to_json ());
982 /* Provide m_checker_states as an object, using names as keys. */
984 json::object
*checkers_obj
= new json::object ();
988 FOR_EACH_VEC_ELT (m_checker_states
, i
, smap
)
989 if (!smap
->is_empty_p ())
990 checkers_obj
->set (ext_state
.get_name (i
), smap
->to_json ());
992 state_obj
->set ("checkers", checkers_obj
);
995 state_obj
->set ("valid", new json::literal (m_valid
));
1000 /* Update this program_state to reflect a top-level call to FUN.
1001 The params will have initial_svalues. */
1004 program_state::push_frame (const extrinsic_state
&ext_state ATTRIBUTE_UNUSED
,
1007 m_region_model
->push_frame (fun
, NULL
, NULL
);
1010 /* Get the current function of this state. */
1013 program_state::get_current_function () const
1015 return m_region_model
->get_current_function ();
1018 /* Determine if following edge SUCC from ENODE is valid within the graph EG
1019 and update this state accordingly in-place.
1021 Return true if the edge can be followed, or false otherwise.
1023 Check for relevant conditionals and switch-values for conditionals
1024 and switch statements, adding the relevant conditions to this state.
1025 Push/pop frames for interprocedural edges and update params/returned
1028 This is the "state" half of exploded_node::on_edge. */
1031 program_state::on_edge (exploded_graph
&eg
,
1032 exploded_node
*enode
,
1033 const superedge
*succ
,
1034 uncertainty_t
*uncertainty
)
1037 const program_point
&point
= enode
->get_point ();
1038 const gimple
*last_stmt
= point
.get_supernode ()->get_last_stmt ();
1040 /* For conditionals and switch statements, add the
1041 relevant conditions (for the specific edge) to new_state;
1042 skip edges for which the resulting constraints
1044 This also updates frame information for call/return superedges.
1045 Adding the relevant conditions for the edge could also trigger
1046 sm-state transitions (e.g. transitions due to ptrs becoming known
1047 to be NULL or non-NULL) */
1049 impl_region_model_context
ctxt (eg
, enode
,
1050 &enode
->get_state (),
1054 if (!m_region_model
->maybe_update_for_edge (*succ
,
1058 logger
* const logger
= eg
.get_logger ();
1060 logger
->log ("edge to SN: %i is impossible"
1061 " due to region_model constraints",
1062 succ
->m_dest
->m_index
);
1066 program_state::detect_leaks (enode
->get_state (), *this,
1067 NULL
, eg
.get_ext_state (),
1073 /* Update this program_state to reflect a call to function
1074 represented by CALL_STMT.
1075 currently used only when the call doesn't have a superedge representing
1076 the call ( like call via a function pointer ) */
1078 program_state::push_call (exploded_graph
&eg
,
1079 exploded_node
*enode
,
1080 const gcall
*call_stmt
,
1081 uncertainty_t
*uncertainty
)
1084 const program_point
&point
= enode
->get_point ();
1085 const gimple
*last_stmt
= point
.get_supernode ()->get_last_stmt ();
1087 impl_region_model_context
ctxt (eg
, enode
,
1088 &enode
->get_state (),
1093 m_region_model
->update_for_gcall (call_stmt
, &ctxt
);
1096 /* Update this program_state to reflect a return from function
1097 call to which is represented by CALL_STMT.
1098 currently used only when the call doesn't have a superedge representing
1101 program_state::returning_call (exploded_graph
&eg
,
1102 exploded_node
*enode
,
1103 const gcall
*call_stmt
,
1104 uncertainty_t
*uncertainty
)
1107 const program_point
&point
= enode
->get_point ();
1108 const gimple
*last_stmt
= point
.get_supernode ()->get_last_stmt ();
1110 impl_region_model_context
ctxt (eg
, enode
,
1111 &enode
->get_state (),
1116 m_region_model
->update_for_return_gcall (call_stmt
, &ctxt
);
1119 /* Generate a simpler version of THIS, discarding state that's no longer
1121 The idea is that we're more likely to be able to consolidate
1122 multiple (point, state) into single exploded_nodes if we discard
1123 irrelevant state (e.g. at the end of functions). */
1126 program_state::prune_for_point (exploded_graph
&eg
,
1127 const program_point
&point
,
1128 exploded_node
*enode_for_diag
,
1129 uncertainty_t
*uncertainty
) const
1131 logger
* const logger
= eg
.get_logger ();
1134 function
*fun
= point
.get_function ();
1138 program_state
new_state (*this);
1140 const state_purge_map
*pm
= eg
.get_purge_map ();
1143 unsigned num_ssas_purged
= 0;
1144 unsigned num_decls_purged
= 0;
1145 auto_vec
<const decl_region
*> regs
;
1146 new_state
.m_region_model
->get_regions_for_current_frame (®s
);
1147 regs
.qsort (region::cmp_ptr_ptr
);
1149 const decl_region
*reg
;
1150 FOR_EACH_VEC_ELT (regs
, i
, reg
)
1152 const tree node
= reg
->get_decl ();
1153 if (TREE_CODE (node
) == SSA_NAME
)
1155 const tree ssa_name
= node
;
1156 const state_purge_per_ssa_name
&per_ssa
1157 = pm
->get_data_for_ssa_name (node
);
1158 if (!per_ssa
.needed_at_point_p (point
.get_function_point ()))
1160 /* Don't purge bindings of SSA names to svalues
1161 that have unpurgable sm-state, so that leaks are
1162 reported at the end of the function, rather than
1163 at the last place that such an SSA name is referred to.
1165 But do purge them for temporaries (when SSA_NAME_VAR is
1166 NULL), so that we report for cases where a leak happens when
1167 a variable is overwritten with another value, so that the leak
1168 is reported at the point of overwrite, rather than having
1169 temporaries keep the value reachable until the frame is
1172 = new_state
.m_region_model
->get_store_value (reg
, NULL
);
1173 if (!new_state
.can_purge_p (eg
.get_ext_state (), sval
)
1174 && SSA_NAME_VAR (ssa_name
))
1176 /* (currently only state maps can keep things
1179 logger
->log ("not purging binding for %qE"
1180 " (used by state map)", ssa_name
);
1184 new_state
.m_region_model
->purge_region (reg
);
1190 const tree decl
= node
;
1191 gcc_assert (TREE_CODE (node
) == VAR_DECL
1192 || TREE_CODE (node
) == PARM_DECL
1193 || TREE_CODE (node
) == RESULT_DECL
);
1194 if (const state_purge_per_decl
*per_decl
1195 = pm
->get_any_data_for_decl (decl
))
1196 if (!per_decl
->needed_at_point_p (point
.get_function_point ()))
1198 /* Don't purge bindings of decls if there are svalues
1199 that have unpurgable sm-state within the decl's cluster,
1200 so that leaks are reported at the end of the function,
1201 rather than at the last place that such a decl is
1203 if (!new_state
.can_purge_base_region_p (eg
.get_ext_state (),
1206 /* (currently only state maps can keep things
1209 logger
->log ("not purging binding for %qE"
1210 " (value in binding used by state map)",
1215 new_state
.m_region_model
->purge_region (reg
);
1221 if (num_ssas_purged
> 0 || num_decls_purged
> 0)
1225 logger
->log ("num_ssas_purged: %i", num_ssas_purged
);
1226 logger
->log ("num_decl_purged: %i", num_decls_purged
);
1228 impl_region_model_context
ctxt (eg
, enode_for_diag
,
1233 detect_leaks (*this, new_state
, NULL
, eg
.get_ext_state (), &ctxt
);
1237 new_state
.m_region_model
->canonicalize ();
1242 /* Return true if there are no unpurgeable bindings within BASE_REG. */
1245 program_state::can_purge_base_region_p (const extrinsic_state
&ext_state
,
1246 const region
*base_reg
) const
1248 binding_cluster
*cluster
1249 = m_region_model
->get_store ()->get_cluster (base_reg
);
1253 for (auto iter
: *cluster
)
1255 const svalue
*sval
= iter
.second
;
1256 if (!can_purge_p (ext_state
, sval
))
1263 /* Get a representative tree to use for describing SVAL. */
1266 program_state::get_representative_tree (const svalue
*sval
) const
1268 gcc_assert (m_region_model
);
1269 return m_region_model
->get_representative_tree (sval
);
1272 /* Attempt to merge this state with OTHER, both at POINT.
1273 Write the result to *OUT.
1274 If the states were merged successfully, return true. */
1277 program_state::can_merge_with_p (const program_state
&other
,
1278 const extrinsic_state
&ext_state
,
1279 const program_point
&point
,
1280 program_state
*out
) const
1283 gcc_assert (m_region_model
);
1285 /* Early reject if there are sm-differences between the states. */
1288 FOR_EACH_VEC_ELT (out
->m_checker_states
, i
, smap
)
1289 if (*m_checker_states
[i
] != *other
.m_checker_states
[i
])
1292 /* Attempt to merge the region_models. */
1293 if (!m_region_model
->can_merge_with_p (*other
.m_region_model
,
1295 out
->m_region_model
,
1300 /* Copy m_checker_states to OUT. */
1301 FOR_EACH_VEC_ELT (out
->m_checker_states
, i
, smap
)
1304 out
->m_checker_states
[i
] = m_checker_states
[i
]->clone ();
1307 out
->m_region_model
->canonicalize ();
1312 /* Assert that this object is valid. */
1315 program_state::validate (const extrinsic_state
&ext_state
) const
1317 /* Skip this in a release build. */
1322 gcc_assert (m_checker_states
.length () == ext_state
.get_num_checkers ());
1323 m_region_model
->validate ();
1327 log_set_of_svalues (logger
*logger
, const char *name
,
1328 const svalue_set
&set
)
1331 logger
->inc_indent ();
1332 auto_vec
<const svalue
*> sval_vecs (set
.elements ());
1333 for (svalue_set::iterator iter
= set
.begin ();
1334 iter
!= set
.end (); ++iter
)
1335 sval_vecs
.quick_push (*iter
);
1336 sval_vecs
.qsort (svalue::cmp_ptr_ptr
);
1339 FOR_EACH_VEC_ELT (sval_vecs
, i
, sval
)
1341 logger
->start_log_line ();
1342 pretty_printer
*pp
= logger
->get_printer ();
1343 if (!flag_dump_noaddr
)
1345 pp_pointer (pp
, sval
);
1346 pp_string (pp
, ": ");
1348 sval
->dump_to_pp (pp
, false);
1349 logger
->end_log_line ();
1351 logger
->dec_indent ();
1354 /* Compare the sets of svalues reachable from each of SRC_STATE and DEST_STATE.
1355 For all svalues that are reachable in SRC_STATE and are not live in
1356 DEST_STATE (whether explicitly reachable in DEST_STATE, or implicitly live
1357 based on the former set), call CTXT->on_svalue_leak for them.
1359 Call on_liveness_change on both the CTXT and on the DEST_STATE's
1360 constraint_manager, purging dead svalues from sm-state and from
1361 constraints, respectively.
1363 This function should be called at each fine-grained state change, not
1364 just at exploded edges. */
1367 program_state::detect_leaks (const program_state
&src_state
,
1368 const program_state
&dest_state
,
1369 const svalue
*extra_sval
,
1370 const extrinsic_state
&ext_state
,
1371 region_model_context
*ctxt
)
1373 logger
*logger
= ext_state
.get_logger ();
1375 const uncertainty_t
*uncertainty
= ctxt
->get_uncertainty ();
1378 pretty_printer
*pp
= logger
->get_printer ();
1379 logger
->start_log_line ();
1380 pp_string (pp
, "src_state: ");
1381 src_state
.dump_to_pp (ext_state
, true, false, pp
);
1382 logger
->end_log_line ();
1383 logger
->start_log_line ();
1384 pp_string (pp
, "dest_state: ");
1385 dest_state
.dump_to_pp (ext_state
, true, false, pp
);
1386 logger
->end_log_line ();
1389 logger
->start_log_line ();
1390 pp_string (pp
, "extra_sval: ");
1391 extra_sval
->dump_to_pp (pp
, true);
1392 logger
->end_log_line ();
1396 logger
->start_log_line ();
1397 pp_string (pp
, "uncertainty: ");
1398 uncertainty
->dump_to_pp (pp
, true);
1399 logger
->end_log_line ();
1403 /* Get svalues reachable from each of src_state and dest_state.
1404 Get svalues *known* to be reachable in src_state.
1405 Pass in uncertainty for dest_state so that we additionally get svalues that
1406 *might* still be reachable in dst_state. */
1407 svalue_set known_src_svalues
;
1408 src_state
.m_region_model
->get_reachable_svalues (&known_src_svalues
,
1410 svalue_set maybe_dest_svalues
;
1411 dest_state
.m_region_model
->get_reachable_svalues (&maybe_dest_svalues
,
1412 extra_sval
, uncertainty
);
1416 log_set_of_svalues (logger
, "src_state known reachable svalues:",
1418 log_set_of_svalues (logger
, "dest_state maybe reachable svalues:",
1419 maybe_dest_svalues
);
1422 auto_vec
<const svalue
*> dead_svals (known_src_svalues
.elements ());
1423 for (svalue_set::iterator iter
= known_src_svalues
.begin ();
1424 iter
!= known_src_svalues
.end (); ++iter
)
1426 const svalue
*sval
= (*iter
);
1427 /* For each sval reachable from SRC_STATE, determine if it is
1428 live in DEST_STATE: either explicitly reachable, implicitly
1429 live based on the set of explicitly reachable svalues,
1430 or possibly reachable as recorded in uncertainty.
1431 Record those that have ceased to be live i.e. were known
1432 to be live, and are now not known to be even possibly-live. */
1433 if (!sval
->live_p (&maybe_dest_svalues
, dest_state
.m_region_model
))
1434 dead_svals
.quick_push (sval
);
1437 /* Call CTXT->on_svalue_leak on all svals in SRC_STATE that have ceased
1438 to be live, sorting them first to ensure deterministic behavior. */
1439 dead_svals
.qsort (svalue::cmp_ptr_ptr
);
1442 FOR_EACH_VEC_ELT (dead_svals
, i
, sval
)
1443 ctxt
->on_svalue_leak (sval
);
1445 /* Purge dead svals from sm-state. */
1446 ctxt
->on_liveness_change (maybe_dest_svalues
,
1447 dest_state
.m_region_model
);
1449 /* Purge dead svals from constraints. */
1450 dest_state
.m_region_model
->get_constraints ()->on_liveness_change
1451 (maybe_dest_svalues
, dest_state
.m_region_model
);
1453 /* Purge dead heap-allocated regions from dynamic extents. */
1454 for (const svalue
*sval
: dead_svals
)
1455 if (const region
*reg
= sval
->maybe_get_region ())
1456 if (reg
->get_kind () == RK_HEAP_ALLOCATED
)
1457 dest_state
.m_region_model
->unset_dynamic_extents (reg
);
1460 /* Attempt to to use R to replay SUMMARY into this object.
1461 Return true if it is possible. */
1464 program_state::replay_call_summary (call_summary_replay
&r
,
1465 const program_state
&summary
)
1467 if (!m_region_model
->replay_call_summary (r
, *summary
.m_region_model
))
1470 for (unsigned sm_idx
= 0; sm_idx
< m_checker_states
.length (); sm_idx
++)
1472 const sm_state_map
*summary_sm_map
= summary
.m_checker_states
[sm_idx
];
1473 m_checker_states
[sm_idx
]->replay_call_summary (r
, *summary_sm_map
);
1476 if (!summary
.m_valid
)
1482 /* Handle calls to "__analyzer_dump_state". */
1485 program_state::impl_call_analyzer_dump_state (const gcall
*call
,
1486 const extrinsic_state
&ext_state
,
1487 region_model_context
*ctxt
)
1489 call_details
cd (call
, m_region_model
, ctxt
);
1490 const char *sm_name
= cd
.get_arg_string_literal (0);
1493 error_at (call
->location
, "cannot determine state machine");
1497 if (!ext_state
.get_sm_idx_by_name (sm_name
, &sm_idx
))
1499 error_at (call
->location
, "unrecognized state machine %qs", sm_name
);
1502 const sm_state_map
*smap
= m_checker_states
[sm_idx
];
1504 const svalue
*sval
= cd
.get_arg_svalue (1);
1506 /* Strip off cast to int (due to variadic args). */
1507 if (const svalue
*cast
= sval
->maybe_undo_cast ())
1510 state_machine::state_t state
= smap
->get_state (sval
, ext_state
);
1511 warning_at (call
->location
, 0, "state: %qs", state
->get_name ());
1516 namespace selftest
{
1518 /* Tests for sm_state_map. */
1521 test_sm_state_map ()
1523 tree x
= build_global_decl ("x", integer_type_node
);
1524 tree y
= build_global_decl ("y", integer_type_node
);
1525 tree z
= build_global_decl ("z", integer_type_node
);
1527 state_machine
*sm
= make_malloc_state_machine (NULL
);
1528 auto_delete_vec
<state_machine
> checkers
;
1529 checkers
.safe_push (sm
);
1531 extrinsic_state
ext_state (checkers
, &eng
);
1532 state_machine::state_t start
= sm
->get_start_state ();
1534 /* Test setting states on svalue_id instances directly. */
1536 const state_machine::state
test_state_42 ("test state 42", 42);
1537 const state_machine::state_t TEST_STATE_42
= &test_state_42
;
1538 region_model_manager mgr
;
1539 region_model
model (&mgr
);
1540 const svalue
*x_sval
= model
.get_rvalue (x
, NULL
);
1541 const svalue
*y_sval
= model
.get_rvalue (y
, NULL
);
1542 const svalue
*z_sval
= model
.get_rvalue (z
, NULL
);
1544 sm_state_map
map (*sm
);
1545 ASSERT_TRUE (map
.is_empty_p ());
1546 ASSERT_EQ (map
.get_state (x_sval
, ext_state
), start
);
1548 map
.impl_set_state (x_sval
, TEST_STATE_42
, z_sval
, ext_state
);
1549 ASSERT_EQ (map
.get_state (x_sval
, ext_state
), TEST_STATE_42
);
1550 ASSERT_EQ (map
.get_origin (x_sval
, ext_state
), z_sval
);
1551 ASSERT_EQ (map
.get_state (y_sval
, ext_state
), start
);
1552 ASSERT_FALSE (map
.is_empty_p ());
1554 map
.impl_set_state (y_sval
, 0, z_sval
, ext_state
);
1555 ASSERT_EQ (map
.get_state (y_sval
, ext_state
), start
);
1557 map
.impl_set_state (x_sval
, 0, z_sval
, ext_state
);
1558 ASSERT_EQ (map
.get_state (x_sval
, ext_state
), start
);
1559 ASSERT_TRUE (map
.is_empty_p ());
1562 const state_machine::state
test_state_5 ("test state 5", 5);
1563 const state_machine::state_t TEST_STATE_5
= &test_state_5
;
1565 /* Test setting states via equivalence classes. */
1567 region_model_manager mgr
;
1568 region_model
model (&mgr
);
1569 const svalue
*x_sval
= model
.get_rvalue (x
, NULL
);
1570 const svalue
*y_sval
= model
.get_rvalue (y
, NULL
);
1571 const svalue
*z_sval
= model
.get_rvalue (z
, NULL
);
1573 sm_state_map
map (*sm
);
1574 ASSERT_TRUE (map
.is_empty_p ());
1575 ASSERT_EQ (map
.get_state (x_sval
, ext_state
), start
);
1576 ASSERT_EQ (map
.get_state (y_sval
, ext_state
), start
);
1578 model
.add_constraint (x
, EQ_EXPR
, y
, NULL
);
1580 /* Setting x to a state should also update y, as they
1581 are in the same equivalence class. */
1582 map
.set_state (&model
, x_sval
, TEST_STATE_5
, z_sval
, ext_state
);
1583 ASSERT_EQ (map
.get_state (x_sval
, ext_state
), TEST_STATE_5
);
1584 ASSERT_EQ (map
.get_state (y_sval
, ext_state
), TEST_STATE_5
);
1585 ASSERT_EQ (map
.get_origin (x_sval
, ext_state
), z_sval
);
1586 ASSERT_EQ (map
.get_origin (y_sval
, ext_state
), z_sval
);
1589 /* Test equality and hashing. */
1591 region_model_manager mgr
;
1592 region_model
model (&mgr
);
1593 const svalue
*y_sval
= model
.get_rvalue (y
, NULL
);
1594 const svalue
*z_sval
= model
.get_rvalue (z
, NULL
);
1596 sm_state_map
map0 (*sm
);
1597 sm_state_map
map1 (*sm
);
1598 sm_state_map
map2 (*sm
);
1600 ASSERT_EQ (map0
.hash (), map1
.hash ());
1601 ASSERT_EQ (map0
, map1
);
1603 map1
.impl_set_state (y_sval
, TEST_STATE_5
, z_sval
, ext_state
);
1604 ASSERT_NE (map0
.hash (), map1
.hash ());
1605 ASSERT_NE (map0
, map1
);
1607 /* Make the same change to map2. */
1608 map2
.impl_set_state (y_sval
, TEST_STATE_5
, z_sval
, ext_state
);
1609 ASSERT_EQ (map1
.hash (), map2
.hash ());
1610 ASSERT_EQ (map1
, map2
);
1613 /* Equality and hashing shouldn't depend on ordering. */
1615 const state_machine::state
test_state_2 ("test state 2", 2);
1616 const state_machine::state_t TEST_STATE_2
= &test_state_2
;
1617 const state_machine::state
test_state_3 ("test state 3", 3);
1618 const state_machine::state_t TEST_STATE_3
= &test_state_3
;
1619 sm_state_map
map0 (*sm
);
1620 sm_state_map
map1 (*sm
);
1621 sm_state_map
map2 (*sm
);
1623 ASSERT_EQ (map0
.hash (), map1
.hash ());
1624 ASSERT_EQ (map0
, map1
);
1626 region_model_manager mgr
;
1627 region_model
model (&mgr
);
1628 const svalue
*x_sval
= model
.get_rvalue (x
, NULL
);
1629 const svalue
*y_sval
= model
.get_rvalue (y
, NULL
);
1630 const svalue
*z_sval
= model
.get_rvalue (z
, NULL
);
1632 map1
.impl_set_state (x_sval
, TEST_STATE_2
, NULL
, ext_state
);
1633 map1
.impl_set_state (y_sval
, TEST_STATE_3
, NULL
, ext_state
);
1634 map1
.impl_set_state (z_sval
, TEST_STATE_2
, NULL
, ext_state
);
1636 map2
.impl_set_state (z_sval
, TEST_STATE_2
, NULL
, ext_state
);
1637 map2
.impl_set_state (y_sval
, TEST_STATE_3
, NULL
, ext_state
);
1638 map2
.impl_set_state (x_sval
, TEST_STATE_2
, NULL
, ext_state
);
1640 ASSERT_EQ (map1
.hash (), map2
.hash ());
1641 ASSERT_EQ (map1
, map2
);
1644 // TODO: coverage for purging
1647 /* Check program_state works as expected. */
1650 test_program_state_1 ()
1652 /* Create a program_state for a global ptr "p" that has
1653 malloc sm-state, pointing to a region on the heap. */
1654 tree p
= build_global_decl ("p", ptr_type_node
);
1656 state_machine
*sm
= make_malloc_state_machine (NULL
);
1657 const state_machine::state_t UNCHECKED_STATE
1658 = sm
->get_state_by_name ("unchecked");
1659 auto_delete_vec
<state_machine
> checkers
;
1660 checkers
.safe_push (sm
);
1663 extrinsic_state
ext_state (checkers
, &eng
);
1664 region_model_manager
*mgr
= eng
.get_model_manager ();
1665 program_state
s (ext_state
);
1666 region_model
*model
= s
.m_region_model
;
1667 const svalue
*size_in_bytes
1668 = mgr
->get_or_create_unknown_svalue (size_type_node
);
1669 const region
*new_reg
1670 = model
->create_region_for_heap_alloc (size_in_bytes
, NULL
);
1671 const svalue
*ptr_sval
= mgr
->get_ptr_svalue (ptr_type_node
, new_reg
);
1672 model
->set_value (model
->get_lvalue (p
, NULL
),
1674 sm_state_map
*smap
= s
.m_checker_states
[0];
1676 smap
->impl_set_state (ptr_sval
, UNCHECKED_STATE
, NULL
, ext_state
);
1677 ASSERT_EQ (smap
->get_state (ptr_sval
, ext_state
), UNCHECKED_STATE
);
1680 /* Check that program_state works for string literals. */
1683 test_program_state_2 ()
1685 /* Create a program_state for a global ptr "p" that points to
1686 a string constant. */
1687 tree p
= build_global_decl ("p", ptr_type_node
);
1689 tree string_cst_ptr
= build_string_literal (4, "foo");
1691 auto_delete_vec
<state_machine
> checkers
;
1693 extrinsic_state
ext_state (checkers
, &eng
);
1695 program_state
s (ext_state
);
1696 region_model
*model
= s
.m_region_model
;
1697 const region
*p_reg
= model
->get_lvalue (p
, NULL
);
1698 const svalue
*str_sval
= model
->get_rvalue (string_cst_ptr
, NULL
);
1699 model
->set_value (p_reg
, str_sval
, NULL
);
1702 /* Verify that program_states with identical sm-state can be merged,
1703 and that the merged program_state preserves the sm-state. */
1706 test_program_state_merging ()
1708 /* Create a program_state for a global ptr "p" that has
1709 malloc sm-state, pointing to a region on the heap. */
1710 tree p
= build_global_decl ("p", ptr_type_node
);
1713 region_model_manager
*mgr
= eng
.get_model_manager ();
1714 program_point
point (program_point::origin (*mgr
));
1715 auto_delete_vec
<state_machine
> checkers
;
1716 checkers
.safe_push (make_malloc_state_machine (NULL
));
1717 extrinsic_state
ext_state (checkers
, &eng
);
1719 program_state
s0 (ext_state
);
1720 uncertainty_t uncertainty
;
1721 impl_region_model_context
ctxt (&s0
, ext_state
, &uncertainty
);
1723 region_model
*model0
= s0
.m_region_model
;
1724 const svalue
*size_in_bytes
1725 = mgr
->get_or_create_unknown_svalue (size_type_node
);
1726 const region
*new_reg
1727 = model0
->create_region_for_heap_alloc (size_in_bytes
, NULL
);
1728 const svalue
*ptr_sval
= mgr
->get_ptr_svalue (ptr_type_node
, new_reg
);
1729 model0
->set_value (model0
->get_lvalue (p
, &ctxt
),
1731 sm_state_map
*smap
= s0
.m_checker_states
[0];
1732 const state_machine::state
test_state ("test state", 0);
1733 const state_machine::state_t TEST_STATE
= &test_state
;
1734 smap
->impl_set_state (ptr_sval
, TEST_STATE
, NULL
, ext_state
);
1735 ASSERT_EQ (smap
->get_state (ptr_sval
, ext_state
), TEST_STATE
);
1737 model0
->canonicalize ();
1739 /* Verify that canonicalization preserves sm-state. */
1740 ASSERT_EQ (smap
->get_state (model0
->get_rvalue (p
, NULL
), ext_state
),
1743 /* Make a copy of the program_state. */
1744 program_state
s1 (s0
);
1747 /* We have two identical states with "p" pointing to a heap region
1748 with the given sm-state.
1749 They ought to be mergeable, preserving the sm-state. */
1750 program_state
merged (ext_state
);
1751 ASSERT_TRUE (s0
.can_merge_with_p (s1
, ext_state
, point
, &merged
));
1752 merged
.validate (ext_state
);
1754 /* Verify that the merged state has the sm-state for "p". */
1755 region_model
*merged_model
= merged
.m_region_model
;
1756 sm_state_map
*merged_smap
= merged
.m_checker_states
[0];
1757 ASSERT_EQ (merged_smap
->get_state (merged_model
->get_rvalue (p
, NULL
),
1761 /* Try canonicalizing. */
1762 merged
.m_region_model
->canonicalize ();
1763 merged
.validate (ext_state
);
1765 /* Verify that the merged state still has the sm-state for "p". */
1766 ASSERT_EQ (merged_smap
->get_state (merged_model
->get_rvalue (p
, NULL
),
1770 /* After canonicalization, we ought to have equality with the inputs. */
1771 ASSERT_EQ (s0
, merged
);
1774 /* Verify that program_states with different global-state in an sm-state
1778 test_program_state_merging_2 ()
1781 region_model_manager
*mgr
= eng
.get_model_manager ();
1782 program_point
point (program_point::origin (*mgr
));
1783 auto_delete_vec
<state_machine
> checkers
;
1784 checkers
.safe_push (make_signal_state_machine (NULL
));
1785 extrinsic_state
ext_state (checkers
, &eng
);
1787 const state_machine::state
test_state_0 ("test state 0", 0);
1788 const state_machine::state
test_state_1 ("test state 1", 1);
1789 const state_machine::state_t TEST_STATE_0
= &test_state_0
;
1790 const state_machine::state_t TEST_STATE_1
= &test_state_1
;
1792 program_state
s0 (ext_state
);
1794 sm_state_map
*smap0
= s0
.m_checker_states
[0];
1795 smap0
->set_global_state (TEST_STATE_0
);
1796 ASSERT_EQ (smap0
->get_global_state (), TEST_STATE_0
);
1799 program_state
s1 (ext_state
);
1801 sm_state_map
*smap1
= s1
.m_checker_states
[0];
1802 smap1
->set_global_state (TEST_STATE_1
);
1803 ASSERT_EQ (smap1
->get_global_state (), TEST_STATE_1
);
1808 /* They ought to not be mergeable. */
1809 program_state
merged (ext_state
);
1810 ASSERT_FALSE (s0
.can_merge_with_p (s1
, ext_state
, point
, &merged
));
1813 /* Run all of the selftests within this file. */
1816 analyzer_program_state_cc_tests ()
1818 test_sm_state_map ();
1819 test_program_state_1 ();
1820 test_program_state_2 ();
1821 test_program_state_merging ();
1822 test_program_state_merging_2 ();
1825 } // namespace selftest
1827 #endif /* CHECKING_P */
1831 #endif /* #if ENABLE_ANALYZER */