| /* Classes for representing the state of interest at a given path of analysis. | |
| Copyright (C) 2019-2026 Free Software Foundation, Inc. | |
| Contributed by David Malcolm <dmalcolm@redhat.com>. | |
| This file is part of GCC. | |
| GCC is free software; you can redistribute it and/or modify it | |
| under the terms of the GNU General Public License as published by | |
| the Free Software Foundation; either version 3, or (at your option) | |
| any later version. | |
| GCC is distributed in the hope that it will be useful, but | |
| WITHOUT ANY WARRANTY; without even the implied warranty of | |
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
| General Public License for more details. | |
| You should have received a copy of the GNU General Public License | |
| along with GCC; see the file COPYING3. If not see | |
| <http://www.gnu.org/licenses/>. */ | |
| #include "analyzer/common.h" | |
| #include "sbitmap.h" | |
| #include "ordered-hash-map.h" | |
| #include "selftest.h" | |
| #include "cfg.h" | |
| #include "gimple-iterator.h" | |
| #include "cgraph.h" | |
| #include "digraph.h" | |
| #include "diagnostics/event-id.h" | |
| #include "diagnostics/state-graphs.h" | |
| #include "graphviz.h" | |
| #include "text-art/tree-widget.h" | |
| #include "text-art/dump.h" | |
| #include "analyzer/analyzer-logging.h" | |
| #include "analyzer/sm.h" | |
| #include "analyzer/call-string.h" | |
| #include "analyzer/program-point.h" | |
| #include "analyzer/store.h" | |
| #include "analyzer/region-model.h" | |
| #include "analyzer/program-state.h" | |
| #include "analyzer/constraint-manager.h" | |
| #include "analyzer/pending-diagnostic.h" | |
| #include "analyzer/diagnostic-manager.h" | |
| #include "analyzer/supergraph.h" | |
| #include "analyzer/program-state.h" | |
| #include "analyzer/exploded-graph.h" | |
| #include "analyzer/state-purge.h" | |
| #include "analyzer/call-summary.h" | |
| #include "analyzer/analyzer-selftests.h" | |
| #include "analyzer/ana-state-to-diagnostic-state.h" | |
| #include "analyzer/liveness-context.h" | |
| #if ENABLE_ANALYZER | |
| namespace ana { | |
| /* class extrinsic_state. */ | |
| std::unique_ptr<text_art::tree_widget> | |
| extrinsic_state::make_dump_widget (symbolic::node_dump_state &nds) const | |
| { | |
| using text_art::tree_widget; | |
| std::unique_ptr<tree_widget> w | |
| (tree_widget::from_fmt (nds, nullptr, "Extrinsic State")); | |
| unsigned i = 0; | |
| for (auto &checker : m_checkers) | |
| { | |
| std::unique_ptr<tree_widget> cw | |
| (tree_widget::from_fmt (nds, nullptr, "m_checkers[%i]: %qs\n", | |
| ++i, checker->get_name ())); | |
| w->add_child (std::move (cw)); | |
| } | |
| return w; | |
| } | |
| /* Return a new json::object of the form | |
| {"checkers" : array of objects, one for each state_machine}. */ | |
| std::unique_ptr<json::object> | |
| extrinsic_state::to_json () const | |
| { | |
| auto ext_state_obj = std::make_unique<json::object> (); | |
| { | |
| auto checkers_arr = std::make_unique<json::array> (); | |
| for (auto &sm : m_checkers) | |
| checkers_arr->append (sm->to_json ()); | |
| ext_state_obj->set ("checkers", std::move (checkers_arr)); | |
| } | |
| return ext_state_obj; | |
| } | |
| /* Get the region_model_manager for this extrinsic_state. */ | |
| region_model_manager * | |
| extrinsic_state::get_model_manager () const | |
| { | |
| if (m_engine) | |
| return m_engine->get_model_manager (); | |
| else | |
| return nullptr; /* for selftests. */ | |
| } | |
| symbolic::node_manager & | |
| extrinsic_state::get_node_manager () const | |
| { | |
| gcc_assert (m_engine); | |
| return m_engine->get_node_manager (); | |
| } | |
| /* Try to find a state machine named NAME. | |
| If found, return true and write its index to *OUT. | |
| Otherwise return false. */ | |
| bool | |
| extrinsic_state::get_sm_idx_by_name (const char *name, unsigned *out) const | |
| { | |
| for (size_t i = 0; i < m_checkers.size (); ++i) | |
| if (0 == strcmp (name, m_checkers[i]->get_name ())) | |
| { | |
| /* Found NAME. */ | |
| *out = i; | |
| return true; | |
| } | |
| /* NAME not found. */ | |
| return false; | |
| } | |
| /* struct sm_state_map::entry_t. */ | |
| int | |
| sm_state_map::entry_t::cmp (const entry_t &entry_a, const entry_t &entry_b) | |
| { | |
| gcc_assert (entry_a.m_state); | |
| gcc_assert (entry_b.m_state); | |
| if (int cmp_state = ((int)entry_a.m_state->get_id () | |
| - (int)entry_b.m_state->get_id ())) | |
| return cmp_state; | |
| if (entry_a.m_origin && entry_b.m_origin) | |
| return svalue::cmp_ptr (entry_a.m_origin, entry_b.m_origin); | |
| if (entry_a.m_origin) | |
| return 1; | |
| if (entry_b.m_origin) | |
| return -1; | |
| return 0; | |
| } | |
| /* class sm_state_map. */ | |
| /* sm_state_map's ctor. */ | |
| sm_state_map::sm_state_map (const state_machine &sm) | |
| : m_sm (sm), m_map (), m_global_state (sm.get_start_state ()) | |
| { | |
| } | |
| /* Clone the sm_state_map. */ | |
| sm_state_map * | |
| sm_state_map::clone () const | |
| { | |
| return new sm_state_map (*this); | |
| } | |
| /* Print this sm_state_map to PP. | |
| If MODEL is non-NULL, print representative tree values where | |
| available. */ | |
| void | |
| sm_state_map::print (const region_model *model, | |
| bool simple, bool multiline, | |
| pretty_printer *pp) const | |
| { | |
| bool first = true; | |
| if (!multiline) | |
| pp_string (pp, "{"); | |
| if (m_global_state != m_sm.get_start_state ()) | |
| { | |
| if (multiline) | |
| pp_string (pp, " "); | |
| pp_string (pp, "global: "); | |
| m_global_state->dump_to_pp (pp); | |
| if (multiline) | |
| pp_newline (pp); | |
| first = false; | |
| } | |
| auto_vec <const svalue *> keys (m_map.elements ()); | |
| for (map_t::iterator iter = m_map.begin (); | |
| iter != m_map.end (); | |
| ++iter) | |
| keys.quick_push ((*iter).first); | |
| keys.qsort (svalue::cmp_ptr_ptr); | |
| unsigned i; | |
| const svalue *sval; | |
| FOR_EACH_VEC_ELT (keys, i, sval) | |
| { | |
| if (multiline) | |
| pp_string (pp, " "); | |
| else if (!first) | |
| pp_string (pp, ", "); | |
| first = false; | |
| if (!flag_dump_noaddr) | |
| { | |
| pp_pointer (pp, sval); | |
| pp_string (pp, ": "); | |
| } | |
| sval->dump_to_pp (pp, simple); | |
| entry_t e = *const_cast <map_t &> (m_map).get (sval); | |
| pp_string (pp, ": "); | |
| e.m_state->dump_to_pp (pp); | |
| if (model) | |
| if (tree rep = model->get_representative_tree (sval)) | |
| { | |
| pp_string (pp, " ("); | |
| dump_quoted_tree (pp, rep); | |
| pp_character (pp, ')'); | |
| } | |
| if (e.m_origin) | |
| { | |
| pp_string (pp, " (origin: "); | |
| if (!flag_dump_noaddr) | |
| { | |
| pp_pointer (pp, e.m_origin); | |
| pp_string (pp, ": "); | |
| } | |
| e.m_origin->dump_to_pp (pp, simple); | |
| if (model) | |
| if (tree rep = model->get_representative_tree (e.m_origin)) | |
| { | |
| pp_string (pp, " ("); | |
| dump_quoted_tree (pp, rep); | |
| pp_character (pp, ')'); | |
| } | |
| pp_string (pp, ")"); | |
| } | |
| if (multiline) | |
| pp_newline (pp); | |
| } | |
| if (!multiline) | |
| pp_string (pp, "}"); | |
| // TODO: m_map_ubc_to_state | |
| } | |
| /* Dump this object to stderr. */ | |
| DEBUG_FUNCTION void | |
| sm_state_map::dump (bool simple) const | |
| { | |
| tree_dump_pretty_printer pp (stderr); | |
| print (nullptr, simple, true, &pp); | |
| pp_newline (&pp); | |
| } | |
| /* Return a new json::object of the form | |
| {"global" : (optional) value for global state, | |
| SVAL_DESC : value for state}. */ | |
| std::unique_ptr<json::object> | |
| sm_state_map::to_json () const | |
| { | |
| auto map_obj = std::make_unique<json::object> (); | |
| if (m_global_state != m_sm.get_start_state ()) | |
| map_obj->set ("global", m_global_state->to_json ()); | |
| for (map_t::iterator iter = m_map.begin (); | |
| iter != m_map.end (); | |
| ++iter) | |
| { | |
| const svalue *sval = (*iter).first; | |
| entry_t e = (*iter).second; | |
| label_text sval_desc = sval->get_desc (); | |
| map_obj->set (sval_desc.get (), e.m_state->to_json ()); | |
| /* This doesn't yet JSONify e.m_origin. */ | |
| } | |
| // TODO: m_map_ubc_to_state | |
| return map_obj; | |
| } | |
| /* Make a text_art::tree_widget describing this sm_state_map, | |
| using MODEL if non-null to describe svalues. */ | |
| std::unique_ptr<text_art::tree_widget> | |
| sm_state_map::make_dump_widget (symbolic::node_dump_state &nds, | |
| const region_model *) const | |
| { | |
| using text_art::styled_string; | |
| using text_art::tree_widget; | |
| std::unique_ptr<tree_widget> state_widget | |
| (tree_widget::from_fmt (nds, nullptr, | |
| "%qs state machine", m_sm.get_name ())); | |
| if (m_global_state != m_sm.get_start_state ()) | |
| { | |
| pretty_printer the_pp; | |
| pretty_printer * const pp = &the_pp; | |
| pp_format_decoder (pp) = default_tree_printer; | |
| pp_string (pp, "Global State: "); | |
| m_global_state->dump_to_pp (pp); | |
| state_widget->add_child (tree_widget::make (nds, pp)); | |
| } | |
| auto_vec <const svalue *> keys (m_map.elements ()); | |
| for (map_t::iterator iter = m_map.begin (); | |
| iter != m_map.end (); | |
| ++iter) | |
| keys.quick_push ((*iter).first); | |
| keys.qsort (svalue::cmp_ptr_ptr); | |
| unsigned i; | |
| const svalue *sval; | |
| FOR_EACH_VEC_ELT (keys, i, sval) | |
| { | |
| entry_t e = *const_cast <map_t &> (m_map).get (sval); | |
| pretty_printer pp; | |
| pp_format_decoder (&pp) = default_tree_printer; | |
| e.m_state->dump_to_pp (&pp); | |
| std::unique_ptr<tree_widget> per_key_widget | |
| = tree_widget::make (nds, &pp); | |
| per_key_widget->add_child (sval->make_dump_widget (nds)); | |
| state_widget->add_child (std::move (per_key_widget)); | |
| } | |
| for (auto iter : m_map_ubc_to_state) | |
| { | |
| auto *ubc = iter.first; | |
| auto state = iter.second; | |
| pretty_printer pp; | |
| pp_format_decoder (&pp) = default_tree_printer; | |
| state->dump_to_pp (&pp); | |
| std::unique_ptr<tree_widget> per_key_widget | |
| = tree_widget::make (nds, &pp); | |
| per_key_widget->add_child (ubc->make_dump_widget (nds)); | |
| state_widget->add_child (std::move (per_key_widget)); | |
| } | |
| return state_widget; | |
| } | |
| DEBUG_FUNCTION void | |
| sm_state_map::dump () const | |
| { | |
| symbolic::dump_node_tree_to_stderr<sm_state_map> (*this); | |
| } | |
| /* Return true if no states have been set within this map | |
| (all expressions are for the start state). */ | |
| bool | |
| sm_state_map::is_empty_p () const | |
| { | |
| return (m_map.elements () == 0 | |
| && m_global_state == m_sm.get_start_state () | |
| && m_map_ubc_to_state.empty ()); | |
| } | |
| /* Generate a hash value for this sm_state_map. */ | |
| hashval_t | |
| sm_state_map::hash () const | |
| { | |
| hashval_t result = 0; | |
| /* Accumulate the result by xoring a hash for each slot, so that the | |
| result doesn't depend on the ordering of the slots in the map. */ | |
| for (map_t::iterator iter = m_map.begin (); | |
| iter != m_map.end (); | |
| ++iter) | |
| { | |
| inchash::hash hstate; | |
| hstate.add_ptr ((*iter).first); | |
| entry_t e = (*iter).second; | |
| hstate.add_int (e.m_state->get_id ()); | |
| hstate.add_ptr (e.m_origin); | |
| result ^= hstate.end (); | |
| } | |
| result ^= m_global_state->get_id (); | |
| return result; | |
| } | |
| /* Equality operator for sm_state_map. */ | |
| bool | |
| sm_state_map::operator== (const sm_state_map &other) const | |
| { | |
| if (m_global_state != other.m_global_state) | |
| return false; | |
| if (m_map.elements () != other.m_map.elements ()) | |
| return false; | |
| for (map_t::iterator iter = m_map.begin (); | |
| iter != m_map.end (); | |
| ++iter) | |
| { | |
| const svalue *sval = (*iter).first; | |
| entry_t e = (*iter).second; | |
| entry_t *other_slot = const_cast <map_t &> (other.m_map).get (sval); | |
| if (other_slot == nullptr) | |
| return false; | |
| if (e != *other_slot) | |
| return false; | |
| } | |
| if (m_map_ubc_to_state != other.m_map_ubc_to_state) | |
| return false; | |
| gcc_checking_assert (hash () == other.hash ()); | |
| return true; | |
| } | |
| state_machine::state_t | |
| sm_state_map:: | |
| get_any_inherited_state_of_bit_vector (const symbolic::bit_vector &bv, | |
| const extrinsic_state &ext_state, | |
| region_model_manager &rmm) const | |
| { | |
| switch (bv.get_kind ()) | |
| { | |
| default: | |
| gcc_unreachable (); | |
| case symbolic::bit_vector::kind::concat: | |
| break; | |
| case symbolic::bit_vector::kind::conjured: | |
| break; | |
| case symbolic::bit_vector::kind::cropped: | |
| { | |
| auto &cropped_bv | |
| = static_cast<const symbolic::cropped_bit_vector &> (bv); | |
| auto &inner_bv = cropped_bv.get_uncropped_bit_vector (); | |
| return get_any_inherited_state_of_bit_vector (inner_bv, ext_state, rmm); | |
| } | |
| break; | |
| case symbolic::bit_vector::kind::empty: | |
| break; | |
| case symbolic::bit_vector::kind::named_test: | |
| break; | |
| case symbolic::bit_vector::kind::poisoned: | |
| break; | |
| case symbolic::bit_vector::kind::repeated: | |
| break; | |
| case symbolic::bit_vector::kind::svalue: | |
| { | |
| auto &from_sval | |
| = static_cast<const symbolic::bit_vector_from_svalue &> (bv); | |
| auto &sval = from_sval.get_svalue (); | |
| return get_state (&sval, ext_state); | |
| } | |
| break; | |
| case symbolic::bit_vector::kind::from_ubc: | |
| { | |
| auto &from_ubc | |
| = static_cast<const symbolic::bit_vector_from_ubc &> (bv); | |
| auto &ubc = from_ubc.get_bit_contents (); | |
| auto iter = m_map_ubc_to_state.find (&ubc); | |
| if (iter != m_map_ubc_to_state.end ()) | |
| return iter->second; | |
| if (auto *conjured_bc = ubc.dyn_cast_conjured_bit_contents ()) | |
| { | |
| auto *id_reg = conjured_bc->get_id_region (); | |
| const svalue *id_reg_ptr = rmm.get_ptr_svalue (NULL_TREE, id_reg); | |
| state_machine::state_t parent_state | |
| = get_state (id_reg_ptr, ext_state); | |
| if (parent_state) | |
| return parent_state; | |
| } | |
| if (auto *baseline_bc = ubc.dyn_cast_baseline_bit_contents ()) | |
| { | |
| auto &bkey = baseline_bc->get_baseline_key (); | |
| const region *reg = bkey.m_base_reg; | |
| const svalue *reg_ptr = rmm.get_ptr_svalue (NULL_TREE, reg); | |
| state_machine::state_t parent_state | |
| = get_state (reg_ptr, ext_state); | |
| if (parent_state) | |
| return parent_state; | |
| } | |
| } | |
| break; | |
| case symbolic::bit_vector::kind::tristate: | |
| break; | |
| } | |
| return nullptr; | |
| } | |
| /* Get the state of SVAL within this object. | |
| States default to the start state. */ | |
| state_machine::state_t | |
| sm_state_map::get_state (const svalue *sval, | |
| const extrinsic_state &ext_state) const | |
| { | |
| gcc_assert (sval); | |
| sval = canonicalize_svalue (sval, ext_state); | |
| if (entry_t *slot | |
| = const_cast <map_t &> (m_map).get (sval)) | |
| return slot->m_state; | |
| /* SVAL has no explicit sm-state. | |
| If this sm allows for state inheritance, then SVAL might have implicit | |
| sm-state inherited via a parent. | |
| For example INIT_VAL(foo.field) might inherit taintedness state from | |
| INIT_VAL(foo). */ | |
| if (m_sm.inherited_state_p ()) | |
| if (region_model_manager *mgr = ext_state.get_model_manager ()) | |
| { | |
| if (const initial_svalue *init_sval = sval->dyn_cast_initial_svalue ()) | |
| { | |
| const region *reg = init_sval->get_region (); | |
| /* Try recursing upwards (up to the base region for the | |
| cluster). */ | |
| if (!reg->base_region_p ()) | |
| if (const region *parent_reg = reg->get_parent_region ()) | |
| { | |
| const svalue *parent_init_sval | |
| = mgr->get_or_create_initial_value (parent_reg); | |
| state_machine::state_t parent_state | |
| = get_state (parent_init_sval, ext_state); | |
| if (parent_state) | |
| return parent_state; | |
| } | |
| } | |
| if (auto *from_bv = sval->dyn_cast_svalue_from_bit_vector ()) | |
| if (auto state | |
| = get_any_inherited_state_of_bit_vector | |
| (from_bv->get_bit_vector (), | |
| ext_state, | |
| *mgr)) | |
| return state; | |
| } | |
| if (state_machine::state_t state | |
| = m_sm.alt_get_inherited_state (*this, sval, ext_state)) | |
| return state; | |
| return m_sm.get_default_state (sval); | |
| } | |
| /* Get the "origin" svalue for any state of SVAL. */ | |
| const svalue * | |
| sm_state_map::get_origin (const svalue *sval, | |
| const extrinsic_state &ext_state) const | |
| { | |
| gcc_assert (sval); | |
| sval = canonicalize_svalue (sval, ext_state); | |
| entry_t *slot | |
| = const_cast <map_t &> (m_map).get (sval); | |
| if (slot) | |
| return slot->m_origin; | |
| else | |
| return nullptr; | |
| } | |
| /* Set the state of SID within MODEL to STATE, recording that | |
| the state came from ORIGIN. */ | |
| void | |
| sm_state_map::set_state (region_model *model, | |
| const svalue *sval, | |
| state_machine::state_t state, | |
| const svalue *origin, | |
| const extrinsic_state &ext_state) | |
| { | |
| if (model == nullptr) | |
| return; | |
| /* Reject attempts to set state on UNKNOWN/POISONED. */ | |
| if (!sval->can_have_associated_state_p ()) | |
| return; | |
| equiv_class &ec = model->get_constraints ()->get_equiv_class (sval); | |
| if (!set_state (ec, state, origin, ext_state)) | |
| return; | |
| } | |
| /* Set the state of EC to STATE, recording that the state came from | |
| ORIGIN. | |
| Return true if any states of svalue_ids within EC changed. */ | |
| bool | |
| sm_state_map::set_state (const equiv_class &ec, | |
| state_machine::state_t state, | |
| const svalue *origin, | |
| const extrinsic_state &ext_state) | |
| { | |
| bool any_changed = false; | |
| for (const svalue *sval : ec.m_vars) | |
| any_changed |= impl_set_state (sval, state, origin, ext_state); | |
| return any_changed; | |
| } | |
| /* Set state of SVAL to STATE, bypassing equivalence classes. | |
| Return true if the state changed. */ | |
| bool | |
| sm_state_map::impl_set_state (const svalue *sval, | |
| state_machine::state_t state, | |
| const svalue *origin, | |
| const extrinsic_state &ext_state) | |
| { | |
| sval = canonicalize_svalue (sval, ext_state); | |
| if (get_state (sval, ext_state) == state) | |
| return false; | |
| gcc_assert (sval->can_have_associated_state_p ()); | |
| /* Special-case state 0 as the default value. */ | |
| if (state == 0) | |
| { | |
| if (m_map.get (sval)) | |
| m_map.remove (sval); | |
| return true; | |
| } | |
| gcc_assert (sval); | |
| m_map.put (sval, entry_t (state, origin)); | |
| /* Update m_map_ubc_to_state. */ | |
| if (m_sm.inherited_state_p ()) | |
| if (auto *from_bv = sval->dyn_cast_svalue_from_bit_vector ()) | |
| if (auto *from_ubc | |
| = from_bv->get_bit_vector ().dyn_cast_bit_vector_from_ubc ()) | |
| m_map_ubc_to_state[&from_ubc->get_bit_contents ()] = state; | |
| return true; | |
| } | |
| /* Clear any state for SVAL from this state map. */ | |
| void | |
| sm_state_map::clear_any_state (const svalue *sval) | |
| { | |
| m_map.remove (sval); | |
| // TODO: what about m_map_ubc_to_state? | |
| } | |
| /* Clear all per-svalue state within this state map. */ | |
| void | |
| sm_state_map::clear_all_per_svalue_state () | |
| { | |
| m_map.empty (); | |
| m_map_ubc_to_state.clear (); | |
| } | |
| /* Set the "global" state within this state map to STATE. */ | |
| void | |
| sm_state_map::set_global_state (state_machine::state_t state) | |
| { | |
| m_global_state = state; | |
| } | |
| /* Get the "global" state within this state map. */ | |
| state_machine::state_t | |
| sm_state_map::get_global_state () const | |
| { | |
| return m_global_state; | |
| } | |
| /* Purge any state for SVAL. | |
| If !SM::can_purge_p, then report the state as leaking, | |
| using CTXT. */ | |
| void | |
| sm_state_map::on_svalue_leak (const svalue *sval, | |
| impl_region_model_context *ctxt) | |
| { | |
| if (state_machine::state_t state = get_state (sval, ctxt->m_ext_state)) | |
| { | |
| if (m_sm.can_purge_p (state)) | |
| m_map.remove (sval); | |
| else | |
| ctxt->on_state_leak (m_sm, sval, state); | |
| } | |
| } | |
| /* Purge any state for svalues that aren't live with respect to | |
| LIVENESS_CTXT. */ | |
| void | |
| sm_state_map::on_liveness_change (symbolic::liveness_context &liveness_ctxt, | |
| const extrinsic_state &ext_state, | |
| impl_region_model_context *ctxt) | |
| { | |
| symbolic::node_set<svalue> svals_to_unset; | |
| uncertainty_t *uncertainty = ctxt->get_uncertainty (); | |
| auto_vec<const svalue *> leaked_svals (m_map.elements ()); | |
| for (map_t::iterator iter = m_map.begin (); | |
| iter != m_map.end (); | |
| ++iter) | |
| { | |
| const svalue *iter_sval = (*iter).first; | |
| if (!liveness_ctxt.node_live_p (*iter_sval)) | |
| { | |
| svals_to_unset.insert (iter_sval); | |
| entry_t e = (*iter).second; | |
| if (!m_sm.can_purge_p (e.m_state)) | |
| leaked_svals.quick_push (iter_sval); | |
| } | |
| if (uncertainty) | |
| if (uncertainty->unknown_sm_state_p (iter_sval)) | |
| svals_to_unset.insert (iter_sval); | |
| } | |
| leaked_svals.qsort (svalue::cmp_ptr_ptr); | |
| unsigned i; | |
| const svalue *sval; | |
| FOR_EACH_VEC_ELT (leaked_svals, i, sval) | |
| { | |
| entry_t e = *m_map.get (sval); | |
| ctxt->on_state_leak (m_sm, sval, e.m_state); | |
| } | |
| sm_state_map old_sm_map = *this; | |
| for (auto iter = svals_to_unset.begin (); | |
| iter != svals_to_unset.end (); ++iter) | |
| m_map.remove (*iter); | |
| /* For state machines like "taint" where states can be | |
| alt-inherited from other svalues, ensure that state purging doesn't | |
| make us lose sm-state. | |
| Consider e.g.: | |
| make_tainted(foo); | |
| if (foo.field > 128) | |
| return; | |
| arr[foo.field].f1 = v1; | |
| where the last line is: | |
| (A): _t1 = foo.field; | |
| (B): _t2 = _t1 * sizeof(arr[0]); | |
| (C): [arr + _t2].f1 = val; | |
| At (A), foo is 'tainted' and foo.field is 'has_ub'. | |
| After (B), foo.field's value (in _t1) is no longer directly | |
| within LIVE_SVALUES, so with state purging enabled, we would | |
| erroneously purge the "has_ub" state from the svalue. | |
| Given that _t2's value's state comes from _t1's value's state, | |
| we need to preserve that information. | |
| Hence for all svalues that have had their explicit sm-state unset, | |
| having their sm-state being unset, determine if doing so has changed | |
| their effective state, and if so, explicitly set their state. | |
| For example, in the above, unsetting the "has_ub" for _t1's value means | |
| that _t2's effective value changes from "has_ub" (from alt-inherited | |
| from _t1's value) to "tainted" (inherited from "foo"'s value). | |
| For such cases, preserve the effective state by explicitly setting the | |
| new state. In the above example, this means explicitly setting _t2's | |
| value to the value ("has_ub") it was previously alt-inheriting from _t1's | |
| value. */ | |
| if (m_sm.has_alt_get_inherited_state_p ()) | |
| { | |
| auto_vec<const svalue *> svalues_needing_state; | |
| for (auto unset_sval : svals_to_unset) | |
| { | |
| const state_machine::state_t old_state | |
| = old_sm_map.get_state (unset_sval, ext_state); | |
| const state_machine::state_t new_state | |
| = get_state (unset_sval, ext_state); | |
| if (new_state != old_state) | |
| svalues_needing_state.safe_push (unset_sval); | |
| } | |
| for (auto sval : svalues_needing_state) | |
| { | |
| const state_machine::state_t old_state | |
| = old_sm_map.get_state (sval, ext_state); | |
| impl_set_state (sval, old_state, nullptr, ext_state); | |
| } | |
| } | |
| } | |
| /* Purge state from VAL (in response to a call to an unknown function). */ | |
| void | |
| sm_state_map::on_unknown_change (const symbolic::value_node &val, | |
| bool is_mutable, | |
| const extrinsic_state &ext_state) | |
| { | |
| symbolic::node_set<svalue> svals_to_unset; | |
| if (auto *sval = val.dyn_cast_svalue ()) | |
| { | |
| sval = canonicalize_svalue (sval, ext_state); | |
| for (map_t::iterator iter = m_map.begin (); | |
| iter != m_map.end (); | |
| ++iter) | |
| { | |
| const svalue *key = (*iter).first; | |
| entry_t e = (*iter).second; | |
| /* We only want to purge state for some states when things | |
| are mutable. For example, in sm-malloc.cc, an on-stack ptr | |
| doesn't stop being stack-allocated when passed to an unknown fn. */ | |
| if (!m_sm.reset_when_passed_to_unknown_fn_p (e.m_state, is_mutable)) | |
| continue; | |
| if (key == sval) | |
| svals_to_unset.add (key); | |
| /* If we have INIT_VAL(BASE_REG), then unset any INIT_VAL(REG) | |
| for REG within BASE_REG. */ | |
| if (const initial_svalue *init_sval = sval->dyn_cast_initial_svalue ()) | |
| if (const initial_svalue *init_key = key->dyn_cast_initial_svalue ()) | |
| { | |
| const region *changed_reg = init_sval->get_region (); | |
| const region *changed_key = init_key->get_region (); | |
| if (changed_key->get_base_region () == changed_reg) | |
| svals_to_unset.add (key); | |
| } | |
| } | |
| } | |
| else if (auto *bv = val.dyn_cast_bit_vector ()) | |
| { | |
| for (map_t::iterator iter = m_map.begin (); | |
| iter != m_map.end (); | |
| ++iter) | |
| { | |
| const svalue *key = (*iter).first; | |
| entry_t e = (*iter).second; | |
| /* We only want to purge state for some states when things | |
| are mutable. For example, in sm-malloc.cc, an on-stack ptr | |
| doesn't stop being stack-allocated when passed to an unknown fn. */ | |
| if (!m_sm.reset_when_passed_to_unknown_fn_p (e.m_state, is_mutable)) | |
| continue; | |
| if (auto *sval_from_bv = key->dyn_cast_svalue_from_bit_vector ()) | |
| if (&sval_from_bv->get_bit_vector () == bv) | |
| svals_to_unset.add (key); | |
| } | |
| } | |
| else | |
| gcc_unreachable (); | |
| for (auto iter = svals_to_unset.begin (); | |
| iter != svals_to_unset.end (); ++iter) | |
| impl_set_state (*iter, (state_machine::state_t)0, nullptr, ext_state); | |
| } | |
| /* Purge state for things involving NODE. | |
| For use when NODE changes meaning, at the def_stmt on an SSA_NAME. */ | |
| void | |
| sm_state_map::purge_state_involving (const symbolic::node &node, | |
| const extrinsic_state &ext_state) | |
| { | |
| symbolic::node_set<svalue> svals_to_unset; | |
| for (map_t::iterator iter = m_map.begin (); | |
| iter != m_map.end (); | |
| ++iter) | |
| { | |
| const svalue *key = (*iter).first; | |
| entry_t e = (*iter).second; | |
| if (!m_sm.can_purge_p (e.m_state)) | |
| continue; | |
| if (key->involves_p (node)) | |
| svals_to_unset.add (key); | |
| } | |
| for (auto iter = svals_to_unset.begin (); | |
| iter != svals_to_unset.end (); ++iter) | |
| impl_set_state (*iter, (state_machine::state_t)0, nullptr, ext_state); | |
| } | |
| /* Comparator for imposing an order on sm_state_map instances. */ | |
| int | |
| sm_state_map::cmp (const sm_state_map &smap_a, const sm_state_map &smap_b) | |
| { | |
| if (int cmp_count = smap_a.elements () - smap_b.elements ()) | |
| return cmp_count; | |
| auto_vec <const svalue *> keys_a (smap_a.elements ()); | |
| for (map_t::iterator iter = smap_a.begin (); | |
| iter != smap_a.end (); | |
| ++iter) | |
| keys_a.quick_push ((*iter).first); | |
| keys_a.qsort (svalue::cmp_ptr_ptr); | |
| auto_vec <const svalue *> keys_b (smap_b.elements ()); | |
| for (map_t::iterator iter = smap_b.begin (); | |
| iter != smap_b.end (); | |
| ++iter) | |
| keys_b.quick_push ((*iter).first); | |
| keys_b.qsort (svalue::cmp_ptr_ptr); | |
| unsigned i; | |
| const svalue *sval_a; | |
| FOR_EACH_VEC_ELT (keys_a, i, sval_a) | |
| { | |
| const svalue *sval_b = keys_b[i]; | |
| if (int cmp_sval = svalue::cmp_ptr (sval_a, sval_b)) | |
| return cmp_sval; | |
| const entry_t *e_a = const_cast <map_t &> (smap_a.m_map).get (sval_a); | |
| const entry_t *e_b = const_cast <map_t &> (smap_b.m_map).get (sval_b); | |
| if (int cmp_entry = entry_t::cmp (*e_a, *e_b)) | |
| return cmp_entry; | |
| } | |
| // TODO: m_map_ubc_to_state | |
| return 0; | |
| } | |
| /* Canonicalize SVAL before getting/setting it within the map. | |
| Convert all NULL pointers to (void *) to avoid state explosions | |
| involving all of the various (foo *)NULL vs (bar *)NULL. */ | |
| const svalue * | |
| sm_state_map::canonicalize_svalue (const svalue *sval, | |
| const extrinsic_state &ext_state) | |
| { | |
| if (!sval) | |
| return nullptr; | |
| region_model_manager *mgr = ext_state.get_model_manager (); | |
| if (!mgr) | |
| return sval; | |
| if (sval->get_type () && POINTER_TYPE_P (sval->get_type ())) | |
| { | |
| if (tree cst = sval->maybe_get_constant ()) | |
| if (zerop (cst)) | |
| return mgr->get_or_create_constant_svalue (null_pointer_node); | |
| } | |
| /* Strip types from symbolic pointers. */ | |
| if (auto *sym_ptr = sval->maybe_get_symbolic_pointer ()) | |
| return mgr->get_ptr_svalue (ptr_type_node, *sym_ptr); | |
| /* Strip types from svalue_from_bit_vector. */ | |
| if (auto *from_bv = sval->dyn_cast_svalue_from_bit_vector ()) | |
| return mgr->get_svalue_from_bit_vector (NULL_TREE, | |
| from_bv->get_bit_vector ()); | |
| return sval; | |
| } | |
| /* Attempt to merge this state map with OTHER, writing the result | |
| into *OUT. | |
| Return true if the merger was possible, false otherwise. | |
| Normally, only identical state maps can be merged, so that | |
| differences between state maps lead to different enodes | |
| However some state machines may support merging states to | |
| allow for discarding of less important states, and thus avoid | |
| blow-up of the exploded graph. */ | |
| bool | |
| sm_state_map::can_merge_with_p (const sm_state_map &other, | |
| const state_machine &sm, | |
| const extrinsic_state &ext_state, | |
| sm_state_map **out) const | |
| { | |
| /* If identical, then they merge trivially, with a copy. */ | |
| if (*this == other) | |
| { | |
| delete *out; | |
| *out = clone (); | |
| return true; | |
| } | |
| delete *out; | |
| *out = new sm_state_map (sm); | |
| /* Otherwise, attempt to merge element by element. */ | |
| /* Try to merge global state. */ | |
| if (state_machine::state_t merged_global_state | |
| = sm.maybe_get_merged_state (get_global_state (), | |
| other.get_global_state ())) | |
| (*out)->set_global_state (merged_global_state); | |
| else | |
| return false; | |
| /* Try to merge state each svalue's state (for the union | |
| of svalues represented by each smap). | |
| Ignore the origin information. */ | |
| hash_set<const svalue *> svals; | |
| for (auto kv : *this) | |
| svals.add (kv.first); | |
| for (auto kv : other) | |
| svals.add (kv.first); | |
| for (auto sval : svals) | |
| { | |
| state_machine::state_t this_state = get_state (sval, ext_state); | |
| state_machine::state_t other_state = other.get_state (sval, ext_state); | |
| if (state_machine::state_t merged_state | |
| = sm.maybe_get_merged_state (this_state, other_state)) | |
| (*out)->impl_set_state (sval, merged_state, nullptr, ext_state); | |
| else | |
| return false; | |
| } | |
| // TODO: m_map_ubc_to_state | |
| /* Successfully merged all elements. */ | |
| return true; | |
| } | |
| void | |
| sm_state_map::validate (const extrinsic_state &ext_state) const | |
| { | |
| for (auto iter : m_map) | |
| { | |
| const svalue *key = iter.first; | |
| state_machine::state_t state = iter.second.m_state; | |
| const svalue *origin = iter.second.m_origin; | |
| gcc_assert (canonicalize_svalue (key, ext_state) == key); | |
| if (origin) | |
| gcc_assert (canonicalize_svalue (origin, ext_state) == origin); | |
| } | |
| } | |
| /* class program_state. */ | |
| /* program_state's ctor. */ | |
| program_state::program_state (const extrinsic_state &ext_state) | |
| : m_region_model (nullptr), | |
| m_checker_states (ext_state.get_num_checkers ()), | |
| m_valid (true) | |
| { | |
| engine *eng = ext_state.get_engine (); | |
| auto &node_mgr = eng->get_node_manager (); | |
| m_region_model = new region_model (node_mgr); | |
| const int num_states = ext_state.get_num_checkers (); | |
| for (int i = 0; i < num_states; i++) | |
| { | |
| sm_state_map *sm = new sm_state_map (ext_state.get_sm (i)); | |
| m_checker_states.quick_push (sm); | |
| } | |
| } | |
| /* Attempt to use R to replay SUMMARY into this object. | |
| Return true if it is possible. */ | |
| bool | |
| sm_state_map::replay_call_summary (call_summary_replay &r, | |
| const sm_state_map &summary) | |
| { | |
| for (auto kv : summary.m_map) | |
| { | |
| const svalue *summary_sval = kv.first; | |
| const svalue *caller_sval = r.convert_svalue_from_summary (summary_sval); | |
| if (!caller_sval) | |
| continue; | |
| caller_sval = canonicalize_svalue (caller_sval, r.get_ext_state ()); | |
| if (!caller_sval->can_have_associated_state_p ()) | |
| continue; | |
| const svalue *summary_origin = kv.second.m_origin; | |
| const svalue *caller_origin | |
| = (summary_origin | |
| ? r.convert_svalue_from_summary (summary_origin) | |
| : nullptr); | |
| // caller_origin can be nullptr. | |
| m_map.put (caller_sval, entry_t (kv.second.m_state, caller_origin)); | |
| } | |
| m_global_state = summary.m_global_state; | |
| return true; | |
| } | |
| /* program_state's copy ctor. */ | |
| program_state::program_state (const program_state &other) | |
| : m_region_model (new region_model (*other.m_region_model)), | |
| m_checker_states (other.m_checker_states.length ()), | |
| m_valid (true) | |
| { | |
| int i; | |
| sm_state_map *smap; | |
| FOR_EACH_VEC_ELT (other.m_checker_states, i, smap) | |
| m_checker_states.quick_push (smap->clone ()); | |
| } | |
| /* program_state's assignment operator. */ | |
| program_state& | |
| program_state::operator= (const program_state &other) | |
| { | |
| delete m_region_model; | |
| m_region_model = new region_model (*other.m_region_model); | |
| int i; | |
| sm_state_map *smap; | |
| FOR_EACH_VEC_ELT (m_checker_states, i, smap) | |
| delete smap; | |
| m_checker_states.truncate (0); | |
| gcc_assert (m_checker_states.space (other.m_checker_states.length ())); | |
| FOR_EACH_VEC_ELT (other.m_checker_states, i, smap) | |
| m_checker_states.quick_push (smap->clone ()); | |
| m_valid = other.m_valid; | |
| return *this; | |
| } | |
| /* Move constructor for program_state (when building with C++11). */ | |
| program_state::program_state (program_state &&other) | |
| : m_region_model (other.m_region_model), | |
| m_checker_states (other.m_checker_states.length ()) | |
| { | |
| other.m_region_model = nullptr; | |
| int i; | |
| sm_state_map *smap; | |
| FOR_EACH_VEC_ELT (other.m_checker_states, i, smap) | |
| m_checker_states.quick_push (smap); | |
| other.m_checker_states.truncate (0); | |
| m_valid = other.m_valid; | |
| } | |
| /* Move assignment for program_state. */ | |
| program_state& | |
| program_state::operator= (program_state &&other) | |
| { | |
| if (this == &other) | |
| return *this; | |
| delete m_region_model; | |
| m_region_model = other.m_region_model; | |
| other.m_region_model = nullptr; | |
| int i; | |
| sm_state_map *smap; | |
| FOR_EACH_VEC_ELT (m_checker_states, i, smap) | |
| delete smap; | |
| m_checker_states.truncate (0); | |
| gcc_assert (m_checker_states.space (other.m_checker_states.length ())); | |
| FOR_EACH_VEC_ELT (other.m_checker_states, i, smap) | |
| m_checker_states.quick_push (smap); | |
| other.m_checker_states.truncate (0); | |
| m_valid = other.m_valid; | |
| return *this; | |
| } | |
| /* program_state's dtor. */ | |
| program_state::~program_state () | |
| { | |
| delete m_region_model; | |
| } | |
| /* Generate a hash value for this program_state. */ | |
| hashval_t | |
| program_state::hash () const | |
| { | |
| hashval_t result = m_region_model->hash (); | |
| int i; | |
| sm_state_map *smap; | |
| FOR_EACH_VEC_ELT (m_checker_states, i, smap) | |
| result ^= smap->hash (); | |
| return result; | |
| } | |
| /* Equality operator for program_state. | |
| All parts of the program_state (region model, checker states) must | |
| equal their counterparts in OTHER for the two program_states to be | |
| considered equal. */ | |
| bool | |
| program_state::operator== (const program_state &other) const | |
| { | |
| if (!(*m_region_model == *other.m_region_model)) | |
| return false; | |
| int i; | |
| sm_state_map *smap; | |
| FOR_EACH_VEC_ELT (m_checker_states, i, smap) | |
| if (!(*smap == *other.m_checker_states[i])) | |
| return false; | |
| gcc_checking_assert (hash () == other.hash ()); | |
| return true; | |
| } | |
| /* Dump a tree-like representation of this state to stderr. */ | |
| DEBUG_FUNCTION void | |
| program_state::dump () const | |
| { | |
| symbolic::dump_node_tree_to_stderr<program_state> (*this); | |
| } | |
| /* Dump a tree-like representation of this state to LOG. */ | |
| void | |
| program_state::dump_to_logger (logger &log, const char *label) const | |
| { | |
| symbolic::dump_node_tree_to_logger<program_state> (*this, log, label); | |
| } | |
| /* Return a new json::object of the form | |
| {"store" : object for store, | |
| "constraints" : object for constraint_manager, | |
| "curr_frame" : (optional) str for current frame, | |
| "checkers" : { STATE_NAME : object per sm_state_map }, | |
| "valid" : true/false}. */ | |
| std::unique_ptr<json::object> | |
| program_state::to_json (const extrinsic_state &ext_state) const | |
| { | |
| auto state_obj = std::make_unique<json::object> (); | |
| state_obj->set ("store", m_region_model->get_store ()->to_json ()); | |
| state_obj->set ("constraints", | |
| m_region_model->get_constraints ()->to_json ()); | |
| if (m_region_model->get_current_frame ()) | |
| state_obj->set ("curr_frame", | |
| m_region_model->get_current_frame ()->to_json ()); | |
| /* Provide m_checker_states as an object, using names as keys. */ | |
| { | |
| auto checkers_obj = std::make_unique<json::object> (); | |
| int i; | |
| sm_state_map *smap; | |
| FOR_EACH_VEC_ELT (m_checker_states, i, smap) | |
| if (!smap->is_empty_p ()) | |
| checkers_obj->set (ext_state.get_name (i), smap->to_json ()); | |
| state_obj->set ("checkers", std::move (checkers_obj)); | |
| } | |
| state_obj->set_bool ("valid", m_valid); | |
| return state_obj; | |
| } | |
| std::unique_ptr<text_art::tree_widget> | |
| program_state::make_dump_widget (symbolic::node_dump_state &nds, | |
| const char *label) const | |
| { | |
| if (!label) | |
| label = "program_state"; | |
| using text_art::tree_widget; | |
| std::unique_ptr<tree_widget> state_widget | |
| (tree_widget::from_fmt (nds, nullptr, "%s", label)); | |
| state_widget->add_child (m_region_model->make_dump_widget (nds)); | |
| /* Add nodes for any sm_state_maps with state. */ | |
| { | |
| int i; | |
| sm_state_map *smap; | |
| FOR_EACH_VEC_ELT (m_checker_states, i, smap) | |
| if (!smap->is_empty_p ()) | |
| state_widget->add_child (smap->make_dump_widget (nds, m_region_model)); | |
| } | |
| return state_widget; | |
| } | |
| void | |
| program_state::dump_dot (const extrinsic_state &ext_state) const | |
| { | |
| auto state_graph = make_diagnostic_state_graph (ext_state); | |
| gcc_assert (global_dc); | |
| auto logical_loc_mgr = global_dc->get_logical_location_manager (); | |
| gcc_assert (logical_loc_mgr); | |
| auto graph = diagnostics::state_graphs::make_dot_graph (*state_graph, | |
| *logical_loc_mgr); | |
| pretty_printer pp; | |
| dot::writer w (pp); | |
| graph->print (w); | |
| pp_flush (&pp); | |
| } | |
| /* Update this program_state to reflect a top-level call to FUN. | |
| The params will have initial_svalues. */ | |
| void | |
| program_state::push_frame (const extrinsic_state &ext_state ATTRIBUTE_UNUSED, | |
| const function &fun) | |
| { | |
| m_region_model->push_frame (fun, nullptr, nullptr, nullptr); | |
| } | |
| /* Get the current function of this state. */ | |
| const function * | |
| program_state::get_current_function () const | |
| { | |
| return m_region_model->get_current_function (); | |
| } | |
| /* Generate a simpler version of THIS, discarding state that's no longer | |
| relevant at POINT. | |
| The idea is that we're more likely to be able to consolidate | |
| multiple (point, state) into single exploded_nodes if we discard | |
| irrelevant state (e.g. at the end of functions). */ | |
| program_state | |
| program_state::prune_for_point (exploded_graph &eg, | |
| const program_point &point, | |
| exploded_node *enode_for_diag, | |
| uncertainty_t *uncertainty) const | |
| { | |
| logger * const logger = eg.get_logger (); | |
| LOG_SCOPE (logger); | |
| function *fun = point.get_function (); | |
| if (!fun) | |
| return *this; | |
| program_state new_state (*this); | |
| const state_purge_map *pm = eg.get_purge_map (); | |
| if (pm) | |
| { | |
| unsigned num_ssas_purged = 0; | |
| unsigned num_decls_purged = 0; | |
| auto_vec<const decl_region *> regs; | |
| new_state.m_region_model->get_regions_for_current_frame (®s); | |
| regs.qsort (region::cmp_ptr_ptr); | |
| unsigned i; | |
| const decl_region *reg; | |
| FOR_EACH_VEC_ELT (regs, i, reg) | |
| { | |
| const tree node = reg->get_decl (); | |
| if (TREE_CODE (node) == SSA_NAME) | |
| { | |
| const tree ssa_name = node; | |
| const state_purge_per_ssa_name &per_ssa | |
| = pm->get_data_for_ssa_name (node); | |
| if (!per_ssa.needed_at_supernode_p (point.get_supernode ())) | |
| { | |
| /* Don't purge bindings of SSA names to svalues | |
| that have unpurgable sm-state, so that leaks are | |
| reported at the end of the function, rather than | |
| at the last place that such an SSA name is referred to. | |
| But do purge them for temporaries (when SSA_NAME_VAR is | |
| NULL), so that we report for cases where a leak happens when | |
| a variable is overwritten with another value, so that the leak | |
| is reported at the point of overwrite, rather than having | |
| temporaries keep the value reachable until the frame is | |
| popped. */ | |
| const svalue *sval | |
| = new_state.m_region_model->get_store_value (reg, nullptr); | |
| if (!new_state.can_purge_p (eg.get_ext_state (), sval) | |
| && SSA_NAME_VAR (ssa_name)) | |
| { | |
| /* (currently only state maps can keep things | |
| alive). */ | |
| if (logger) | |
| logger->log ("not purging binding for %qE" | |
| " (used by state map)", ssa_name); | |
| continue; | |
| } | |
| new_state.m_region_model->purge_region (reg); | |
| num_ssas_purged++; | |
| } | |
| } | |
| else | |
| { | |
| const tree decl = node; | |
| gcc_assert (TREE_CODE (node) == VAR_DECL | |
| || TREE_CODE (node) == PARM_DECL | |
| || TREE_CODE (node) == RESULT_DECL); | |
| if (const state_purge_per_decl *per_decl | |
| = pm->get_any_data_for_decl (decl)) | |
| if (!per_decl->needed_at_supernode_p (point.get_supernode ())) | |
| { | |
| /* Don't purge bindings of decls if there are svalues | |
| that have unpurgable sm-state within the decl's cluster, | |
| so that leaks are reported at the end of the function, | |
| rather than at the last place that such a decl is | |
| referred to. */ | |
| if (!new_state.can_purge_base_region_p (eg.get_ext_state (), | |
| reg)) | |
| { | |
| /* (currently only state maps can keep things | |
| alive). */ | |
| if (logger) | |
| logger->log ("not purging binding for %qE" | |
| " (value in binding used by state map)", | |
| decl); | |
| continue; | |
| } | |
| new_state.m_region_model->purge_region (reg); | |
| num_decls_purged++; | |
| } | |
| } | |
| } | |
| if (num_ssas_purged > 0 || num_decls_purged > 0) | |
| { | |
| if (logger) | |
| { | |
| logger->log ("num_ssas_purged: %i", num_ssas_purged); | |
| logger->log ("num_decl_purged: %i", num_decls_purged); | |
| } | |
| impl_region_model_context ctxt (eg, enode_for_diag, | |
| this, | |
| &new_state, | |
| uncertainty, | |
| nullptr); | |
| detect_leaks (*this, new_state, nullptr, eg.get_ext_state (), &ctxt); | |
| } | |
| } | |
| new_state.m_region_model->canonicalize (); | |
| return new_state; | |
| } | |
| /* Return true if there are no unpurgeable bindings within BASE_REG. */ | |
| bool | |
| program_state::can_purge_base_region_p (const extrinsic_state &ext_state, | |
| const region *base_reg) const | |
| { | |
| binding_cluster *cluster | |
| = m_region_model->get_store ()->get_cluster (base_reg); | |
| if (!cluster) | |
| return true; | |
| symbolic::node_set<symbolic::value_node> bound_value_nodes; | |
| cluster->for_each_value ([](const symbolic::value_node &val, | |
| void *user_data) -> iter_result | |
| { | |
| auto *bound_value_nodes | |
| = static_cast <symbolic::node_set<symbolic::value_node> *> (user_data); | |
| bound_value_nodes->add (&val); | |
| return iter_result::keep_going; | |
| }, &bound_value_nodes); | |
| if (bound_value_nodes.empty ()) | |
| return true; | |
| auto &bv_mgr | |
| = ext_state.get_node_manager ().get_bit_vector_manager (); | |
| int i; | |
| sm_state_map *smap; | |
| FOR_EACH_VEC_ELT (m_checker_states, i, smap) | |
| for (auto iter : *smap) | |
| { | |
| const svalue *sval = iter.first; | |
| sm_state_map::entry_t e = iter.second; | |
| if (!ext_state.get_sm (i).can_purge_p (e.m_state)) | |
| { | |
| if (bound_value_nodes.contains (sval)) | |
| return false; | |
| if (auto *as_bv = bv_mgr.maybe_get_bit_vector_from_svalue (*sval)) | |
| { | |
| if (bound_value_nodes.contains (as_bv)) | |
| return false; | |
| } | |
| } | |
| } | |
| return true; | |
| } | |
| /* Get a representative tree to use for describing SVAL. */ | |
| tree | |
| program_state::get_representative_tree (const svalue *sval) const | |
| { | |
| gcc_assert (m_region_model); | |
| return m_region_model->get_representative_tree (sval); | |
| } | |
| /* Attempt to merge this state with OTHER, both at POINT. | |
| Write the result to *OUT. | |
| If the states were merged successfully, return true. */ | |
| bool | |
| program_state::can_merge_with_p (const program_state &other, | |
| const extrinsic_state &ext_state, | |
| const program_point &point, | |
| program_state *out) const | |
| { | |
| gcc_assert (out); | |
| gcc_assert (m_region_model); | |
| /* Attempt to merge the sm-states. */ | |
| int i; | |
| sm_state_map *smap; | |
| FOR_EACH_VEC_ELT (out->m_checker_states, i, smap) | |
| if (!m_checker_states[i]->can_merge_with_p (*other.m_checker_states[i], | |
| ext_state.get_sm (i), | |
| ext_state, | |
| &out->m_checker_states[i])) | |
| return false; | |
| /* Attempt to merge the region_models. */ | |
| if (!m_region_model->can_merge_with_p (*other.m_region_model, | |
| point, | |
| out->m_region_model, | |
| &ext_state, | |
| this, &other)) | |
| return false; | |
| out->m_region_model->canonicalize (); | |
| return true; | |
| } | |
| /* Assert that this object is valid. */ | |
| void | |
| program_state::validate (const extrinsic_state &ext_state) const | |
| { | |
| /* Skip this in a release build. */ | |
| #if !CHECKING_P | |
| return; | |
| #endif | |
| gcc_assert (m_checker_states.length () == ext_state.get_num_checkers ()); | |
| m_region_model->validate (); | |
| int i; | |
| sm_state_map *smap; | |
| FOR_EACH_VEC_ELT (m_checker_states, i, smap) | |
| m_checker_states[i]->validate (ext_state); | |
| } | |
| static void | |
| log_set_of_values (logger *logger, const char *name, | |
| const value_set &set) | |
| { | |
| logger->log ("%s", name); | |
| logger->inc_indent (); | |
| auto_vec<const symbolic::value_node *> val_vec (set.size ()); | |
| for (value_set::iterator iter = set.begin (); | |
| iter != set.end (); ++iter) | |
| val_vec.quick_push (*iter); | |
| val_vec.qsort (svalue::cmp_ptr_ptr); | |
| unsigned i; | |
| const symbolic::value_node *val; | |
| FOR_EACH_VEC_ELT (val_vec, i, val) | |
| val->dump_to_logger (*logger); | |
| logger->dec_indent (); | |
| } | |
| // class symbolic::liveness_context | |
| namespace symbolic { | |
| liveness_context::liveness_context (const value_set &known_live_values, | |
| const region_model &model) | |
| : m_model (model) | |
| { | |
| for (auto iter : known_live_values) | |
| set_known_liveness_for_node (*iter, true); | |
| } | |
| bool | |
| liveness_context::node_live_p (const symbolic::value_node &n) | |
| { | |
| /* Do we already know the liveness of N? */ | |
| auto iter = m_known_liveness.find (&n); | |
| if (iter != m_known_liveness.end ()) | |
| return iter->second; | |
| /* Otherwise, determine if SVAL is implicitly live due to being made of | |
| other live svalues. */ | |
| bool implicitly_live = n.implicitly_live_p (*this); | |
| set_known_liveness_for_node (n, implicitly_live); | |
| return implicitly_live; | |
| } | |
| bool | |
| liveness_context::bits_live_p (const bit_vector_from_ubc &bv_from_ubc) | |
| { | |
| return m_model.bits_live_p (bv_from_ubc); | |
| } | |
| /* Consider any pointer to base_reg in LIVENESS_CTXT as keeping it live, so | |
| that different (X*)ptr and (Y*)ptr are effectively the same from | |
| a liveness perspective. */ | |
| bool | |
| liveness_context::known_live_ptr_to_base_region_p (const region &base_reg) const | |
| { | |
| auto iter = m_known_base_regions.find (&base_reg); | |
| if (iter != m_known_base_regions.end ()) | |
| return true; | |
| return false; | |
| } | |
| void | |
| liveness_context::set_known_liveness_for_node (const symbolic::value_node &n, | |
| bool is_live) | |
| { | |
| m_known_liveness.insert ({&n, is_live}); | |
| /* Consider any pointer to a base region as keeping that region live, so | |
| that different (X*)ptr and (Y*)ptr are effectively the same from | |
| a liveness perspective. */ | |
| if (is_live) | |
| if (auto *sval = n.dyn_cast_svalue ()) | |
| if (auto *sym_ptr = sval->maybe_get_symbolic_pointer ()) | |
| m_known_base_regions.insert (&sym_ptr->get_base_region ()); | |
| } | |
| void | |
| liveness_context::dump_to_pp (pretty_printer *pp) const | |
| { | |
| text_art::theme *theme = global_dc->get_diagram_theme (); | |
| symbolic::dump_node_tree_to_pp<liveness_context> | |
| (*this, theme, pp, | |
| true /* show_ids */, | |
| true /* elide_repeated_nodes */); | |
| } | |
| std::unique_ptr<text_art::tree_widget> | |
| liveness_context::make_dump_widget (symbolic::node_dump_state &nds) const | |
| { | |
| using text_art::tree_widget; | |
| std::unique_ptr<tree_widget> widget | |
| = tree_widget::from_fmt (nds, nullptr, "impl_liveness_context"); | |
| for (auto iter : m_known_liveness) | |
| { | |
| const symbolic::value_node *node = iter.first; | |
| bool liveness = iter.second; | |
| const char *prefix = liveness ? "live" : "dead"; | |
| widget->add_child (node->make_dump_widget (nds, prefix)); | |
| } | |
| for (auto iter : m_known_base_regions) | |
| widget->add_child (iter->make_dump_widget (nds, "known region")); | |
| widget->add_child (m_model.make_dump_widget (nds)); | |
| return widget; | |
| } | |
| } // namespace ana::symbolic | |
| /* Compare the sets of svalues reachable from each of SRC_STATE and DEST_STATE. | |
| For all svalues that are reachable in SRC_STATE and are not live in | |
| DEST_STATE (whether explicitly reachable in DEST_STATE, or implicitly live | |
| based on the former set), call CTXT->on_svalue_leak for them. | |
| Call on_liveness_change on both the CTXT and on the DEST_STATE's | |
| constraint_manager, purging dead svalues from sm-state and from | |
| constraints, respectively. | |
| This function should be called at each fine-grained state change, not | |
| just at exploded edges. */ | |
| void | |
| program_state::detect_leaks (const program_state &src_state, | |
| const program_state &dest_state, | |
| const svalue *extra_sval, | |
| const extrinsic_state &ext_state, | |
| region_model_context *ctxt) | |
| { | |
| logger *logger = ext_state.get_logger (); | |
| LOG_SCOPE (logger); | |
| const uncertainty_t *uncertainty = ctxt->get_uncertainty (); | |
| if (logger) | |
| { | |
| src_state.dump_to_logger (*logger, "src_state"); | |
| dest_state.dump_to_logger (*logger, "dest_state"); | |
| if (extra_sval) | |
| { | |
| logger->log ("extra_sval:"); | |
| extra_sval->dump_to_logger (*logger); | |
| } | |
| if (uncertainty) | |
| uncertainty->dump_to_logger (*logger); | |
| } | |
| /* Get svalues reachable from each of src_state and dest_state. | |
| Get svalues *known* to be reachable in src_state. | |
| Pass in uncertainty for dest_state so that we additionally get svalues that | |
| *might* still be reachable in dst_state. */ | |
| value_set known_src_svalues; | |
| src_state.m_region_model->get_reachable_svalues (&known_src_svalues, | |
| nullptr, nullptr); | |
| value_set maybe_dest_svalues; | |
| dest_state.m_region_model->get_reachable_svalues (&maybe_dest_svalues, | |
| extra_sval, uncertainty); | |
| if (logger) | |
| { | |
| log_set_of_values (logger, "src_state known reachable values:", | |
| known_src_svalues); | |
| log_set_of_values (logger, "dest_state maybe reachable values:", | |
| maybe_dest_svalues); | |
| } | |
| symbolic::liveness_context dest_liveness (maybe_dest_svalues, | |
| *dest_state.m_region_model); | |
| auto_vec <const svalue *> dead_svals (known_src_svalues.size ()); | |
| for (value_set::iterator iter = known_src_svalues.begin (); | |
| iter != known_src_svalues.end (); ++iter) | |
| if (auto *sval = (*iter)->dyn_cast_svalue ()) | |
| { | |
| /* For each sval reachable from SRC_STATE, determine if it is | |
| live in DEST_STATE: either explicitly reachable, implicitly | |
| live based on the set of explicitly reachable svalues, | |
| or possibly reachable as recorded in uncertainty. | |
| Record those that have ceased to be live i.e. were known | |
| to be live, and are now not known to be even possibly-live. */ | |
| if (!dest_liveness.node_live_p (*sval)) | |
| dead_svals.quick_push (sval); | |
| } | |
| /* Call CTXT->on_svalue_leak on all svals in SRC_STATE that have ceased | |
| to be live, sorting them first to ensure deterministic behavior. */ | |
| dead_svals.qsort (svalue::cmp_ptr_ptr); | |
| unsigned i; | |
| const svalue *sval; | |
| FOR_EACH_VEC_ELT (dead_svals, i, sval) | |
| ctxt->on_svalue_leak (sval); | |
| /* Purge dead svals from sm-state. */ | |
| ctxt->on_liveness_change (dest_liveness); | |
| /* Purge dead svals from constraints. */ | |
| dest_state.m_region_model->get_constraints ()->on_liveness_change | |
| (dest_liveness); | |
| /* Purge dead heap-allocated regions from dynamic extents. */ | |
| for (const svalue *sval : dead_svals) | |
| if (auto *sym_ptr = sval->maybe_get_symbolic_pointer ()) | |
| { | |
| const region ® = sym_ptr->get_base_region (); | |
| if (reg.get_kind () == RK_HEAP_ALLOCATED) | |
| dest_state.m_region_model->unset_dynamic_extents (®); | |
| } | |
| } | |
| /* Attempt to use R to replay SUMMARY into this object. | |
| Return true if it is possible. */ | |
| bool | |
| program_state::replay_call_summary (call_summary_replay &r, | |
| const program_state &summary) | |
| { | |
| if (!m_region_model->replay_call_summary (r, *summary.m_region_model)) | |
| return false; | |
| for (unsigned sm_idx = 0; sm_idx < m_checker_states.length (); sm_idx++) | |
| { | |
| const sm_state_map *summary_sm_map = summary.m_checker_states[sm_idx]; | |
| m_checker_states[sm_idx]->replay_call_summary (r, *summary_sm_map); | |
| } | |
| if (!summary.m_valid) | |
| m_valid = false; | |
| return true; | |
| } | |
| /* Handle calls to "__analyzer_dump_state". */ | |
| void | |
| program_state::impl_call_analyzer_dump_state (const gcall &call, | |
| const extrinsic_state &ext_state, | |
| region_model_context *ctxt) | |
| { | |
| call_details cd (call, m_region_model, ctxt); | |
| const char *sm_name = cd.get_arg_string_literal (0); | |
| if (!sm_name) | |
| { | |
| error_at (call.location, "cannot determine state machine"); | |
| return; | |
| } | |
| unsigned sm_idx; | |
| if (!ext_state.get_sm_idx_by_name (sm_name, &sm_idx)) | |
| { | |
| error_at (call.location, "unrecognized state machine %qs", sm_name); | |
| return; | |
| } | |
| const sm_state_map *smap = m_checker_states[sm_idx]; | |
| const svalue *sval = cd.get_arg_svalue (1); | |
| /* Strip off cast to int (due to variadic args). */ | |
| if (const svalue *cast = sval->maybe_undo_cast ()) | |
| sval = cast; | |
| state_machine::state_t state = smap->get_state (sval, ext_state); | |
| warning_at (call.location, 0, "state: %qs", state->get_name ()); | |
| } | |
| #if CHECKING_P | |
| namespace selftest { | |
| /* Tests for sm_state_map. */ | |
| static void | |
| test_sm_state_map () | |
| { | |
| tree x = build_global_decl ("x", integer_type_node); | |
| tree y = build_global_decl ("y", integer_type_node); | |
| tree z = build_global_decl ("z", integer_type_node); | |
| std::unique_ptr<state_machine> sm = make_malloc_state_machine (nullptr); | |
| state_machine::state_t start = sm->get_start_state (); | |
| std::vector<std::unique_ptr<state_machine>> checkers; | |
| const state_machine &borrowed_sm = *sm.get (); | |
| checkers.push_back (std::move (sm)); | |
| symbolic::node_manager node_mgr; | |
| engine eng (node_mgr); | |
| extrinsic_state ext_state (std::move (checkers), &eng); | |
| /* Test setting states on svalue_id instances directly. */ | |
| { | |
| const state_machine::state test_state_42 ("test state 42", 42); | |
| const state_machine::state_t TEST_STATE_42 = &test_state_42; | |
| region_model model (node_mgr); | |
| const svalue *x_sval = model.get_rvalue (x, nullptr); | |
| const svalue *y_sval = model.get_rvalue (y, nullptr); | |
| const svalue *z_sval = model.get_rvalue (z, nullptr); | |
| sm_state_map map (borrowed_sm); | |
| ASSERT_TRUE (map.is_empty_p ()); | |
| ASSERT_EQ (map.get_state (x_sval, ext_state), start); | |
| map.impl_set_state (x_sval, TEST_STATE_42, z_sval, ext_state); | |
| ASSERT_EQ (map.get_state (x_sval, ext_state), TEST_STATE_42); | |
| ASSERT_EQ (map.get_origin (x_sval, ext_state), z_sval); | |
| ASSERT_EQ (map.get_state (y_sval, ext_state), start); | |
| ASSERT_FALSE (map.is_empty_p ()); | |
| map.impl_set_state (y_sval, 0, z_sval, ext_state); | |
| ASSERT_EQ (map.get_state (y_sval, ext_state), start); | |
| map.impl_set_state (x_sval, 0, z_sval, ext_state); | |
| ASSERT_EQ (map.get_state (x_sval, ext_state), start); | |
| ASSERT_TRUE (map.is_empty_p ()); | |
| } | |
| const state_machine::state test_state_5 ("test state 5", 5); | |
| const state_machine::state_t TEST_STATE_5 = &test_state_5; | |
| /* Test setting states via equivalence classes. */ | |
| { | |
| region_model model (node_mgr); | |
| const svalue *x_sval = model.get_rvalue (x, nullptr); | |
| const svalue *y_sval = model.get_rvalue (y, nullptr); | |
| const svalue *z_sval = model.get_rvalue (z, nullptr); | |
| sm_state_map map (borrowed_sm); | |
| ASSERT_TRUE (map.is_empty_p ()); | |
| ASSERT_EQ (map.get_state (x_sval, ext_state), start); | |
| ASSERT_EQ (map.get_state (y_sval, ext_state), start); | |
| model.add_constraint (x, EQ_EXPR, y, nullptr); | |
| /* Setting x to a state should also update y, as they | |
| are in the same equivalence class. */ | |
| map.set_state (&model, x_sval, TEST_STATE_5, z_sval, ext_state); | |
| ASSERT_EQ (map.get_state (x_sval, ext_state), TEST_STATE_5); | |
| ASSERT_EQ (map.get_state (y_sval, ext_state), TEST_STATE_5); | |
| ASSERT_EQ (map.get_origin (x_sval, ext_state), z_sval); | |
| ASSERT_EQ (map.get_origin (y_sval, ext_state), z_sval); | |
| } | |
| /* Test equality and hashing. */ | |
| { | |
| region_model model (node_mgr); | |
| const svalue *y_sval = model.get_rvalue (y, nullptr); | |
| const svalue *z_sval = model.get_rvalue (z, nullptr); | |
| sm_state_map map0 (borrowed_sm); | |
| sm_state_map map1 (borrowed_sm); | |
| sm_state_map map2 (borrowed_sm); | |
| ASSERT_EQ (map0.hash (), map1.hash ()); | |
| ASSERT_EQ (map0, map1); | |
| map1.impl_set_state (y_sval, TEST_STATE_5, z_sval, ext_state); | |
| ASSERT_NE (map0.hash (), map1.hash ()); | |
| ASSERT_NE (map0, map1); | |
| /* Make the same change to map2. */ | |
| map2.impl_set_state (y_sval, TEST_STATE_5, z_sval, ext_state); | |
| ASSERT_EQ (map1.hash (), map2.hash ()); | |
| ASSERT_EQ (map1, map2); | |
| } | |
| /* Equality and hashing shouldn't depend on ordering. */ | |
| { | |
| const state_machine::state test_state_2 ("test state 2", 2); | |
| const state_machine::state_t TEST_STATE_2 = &test_state_2; | |
| const state_machine::state test_state_3 ("test state 3", 3); | |
| const state_machine::state_t TEST_STATE_3 = &test_state_3; | |
| sm_state_map map0 (borrowed_sm); | |
| sm_state_map map1 (borrowed_sm); | |
| sm_state_map map2 (borrowed_sm); | |
| ASSERT_EQ (map0.hash (), map1.hash ()); | |
| ASSERT_EQ (map0, map1); | |
| region_model model (node_mgr); | |
| const svalue *x_sval = model.get_rvalue (x, nullptr); | |
| const svalue *y_sval = model.get_rvalue (y, nullptr); | |
| const svalue *z_sval = model.get_rvalue (z, nullptr); | |
| map1.impl_set_state (x_sval, TEST_STATE_2, nullptr, ext_state); | |
| map1.impl_set_state (y_sval, TEST_STATE_3, nullptr, ext_state); | |
| map1.impl_set_state (z_sval, TEST_STATE_2, nullptr, ext_state); | |
| map2.impl_set_state (z_sval, TEST_STATE_2, nullptr, ext_state); | |
| map2.impl_set_state (y_sval, TEST_STATE_3, nullptr, ext_state); | |
| map2.impl_set_state (x_sval, TEST_STATE_2, nullptr, ext_state); | |
| ASSERT_EQ (map1.hash (), map2.hash ()); | |
| ASSERT_EQ (map1, map2); | |
| } | |
| // TODO: coverage for purging | |
| } | |
| /* Check program_state works as expected. */ | |
| static void | |
| test_program_state_1 () | |
| { | |
| /* Create a program_state for a global ptr "p" that has | |
| malloc sm-state, pointing to a region on the heap. */ | |
| tree p = build_global_decl ("p", ptr_type_node); | |
| std::unique_ptr<state_machine> sm = make_malloc_state_machine (nullptr); | |
| const state_machine::state_t UNCHECKED_STATE | |
| = sm->get_state_by_name ("unchecked"); | |
| symbolic::node_manager node_mgr; | |
| auto &mgr = node_mgr.get_region_model_manager (); | |
| engine eng (node_mgr); | |
| extrinsic_state ext_state (std::move (sm), &eng); | |
| program_state s (ext_state); | |
| region_model *model = s.m_region_model; | |
| const svalue *size_in_bytes | |
| = mgr.get_or_create_unknown_svalue (size_type_node); | |
| const region *new_reg | |
| = model->get_or_create_region_for_heap_alloc (size_in_bytes, nullptr); | |
| const svalue *ptr_sval = mgr.get_ptr_svalue (ptr_type_node, new_reg); | |
| model->set_value (model->get_lvalue (p, nullptr), | |
| ptr_sval, nullptr); | |
| sm_state_map *smap = s.m_checker_states[0]; | |
| smap->impl_set_state (ptr_sval, UNCHECKED_STATE, nullptr, ext_state); | |
| ASSERT_EQ (smap->get_state (ptr_sval, ext_state), UNCHECKED_STATE); | |
| } | |
| /* Check that program_state works for string literals. */ | |
| static void | |
| test_program_state_2 () | |
| { | |
| /* Create a program_state for a global ptr "p" that points to | |
| a string constant. */ | |
| tree p = build_global_decl ("p", ptr_type_node); | |
| tree string_cst_ptr = build_string_literal (4, "foo"); | |
| std::vector<std::unique_ptr<state_machine>> checkers; | |
| symbolic::node_manager node_mgr; | |
| engine eng (node_mgr); | |
| extrinsic_state ext_state (std::move (checkers), &eng); | |
| program_state s (ext_state); | |
| region_model *model = s.m_region_model; | |
| const region *p_reg = model->get_lvalue (p, nullptr); | |
| const svalue *str_sval = model->get_rvalue (string_cst_ptr, nullptr); | |
| model->set_value (p_reg, str_sval, nullptr); | |
| } | |
| /* Verify that program_states with identical sm-state can be merged, | |
| and that the merged program_state preserves the sm-state. */ | |
| static void | |
| test_program_state_merging () | |
| { | |
| /* Create a program_state for a global ptr "p" that has | |
| malloc sm-state, pointing to a region on the heap. */ | |
| tree p = build_global_decl ("p", ptr_type_node); | |
| symbolic::node_manager node_mgr; | |
| auto &mgr = node_mgr.get_region_model_manager (); | |
| engine eng (node_mgr); | |
| program_point point (program_point::origin (mgr)); | |
| extrinsic_state ext_state (make_malloc_state_machine (nullptr), | |
| &eng); | |
| program_state s0 (ext_state); | |
| uncertainty_t uncertainty; | |
| impl_region_model_context ctxt (&s0, ext_state, &uncertainty); | |
| region_model *model0 = s0.m_region_model; | |
| const svalue *size_in_bytes | |
| = mgr.get_or_create_unknown_svalue (size_type_node); | |
| const region *new_reg | |
| = model0->get_or_create_region_for_heap_alloc (size_in_bytes, nullptr); | |
| const svalue *ptr_sval = mgr.get_ptr_svalue (ptr_type_node, new_reg); | |
| model0->set_value (model0->get_lvalue (p, &ctxt), | |
| ptr_sval, &ctxt); | |
| sm_state_map *smap = s0.m_checker_states[0]; | |
| const state_machine::state test_state ("test state", 0); | |
| const state_machine::state_t TEST_STATE = &test_state; | |
| smap->impl_set_state (ptr_sval, TEST_STATE, nullptr, ext_state); | |
| ASSERT_EQ (smap->get_state (ptr_sval, ext_state), TEST_STATE); | |
| model0->canonicalize (); | |
| /* Verify that canonicalization preserves sm-state. */ | |
| ASSERT_EQ (smap->get_state (model0->get_rvalue (p, nullptr), ext_state), | |
| TEST_STATE); | |
| /* Make a copy of the program_state. */ | |
| program_state s1 (s0); | |
| ASSERT_EQ (s0, s1); | |
| /* We have two identical states with "p" pointing to a heap region | |
| with the given sm-state. | |
| They ought to be mergeable, preserving the sm-state. */ | |
| program_state merged (ext_state); | |
| ASSERT_TRUE (s0.can_merge_with_p (s1, ext_state, point, &merged)); | |
| merged.validate (ext_state); | |
| /* Verify that the merged state has the sm-state for "p". */ | |
| region_model *merged_model = merged.m_region_model; | |
| sm_state_map *merged_smap = merged.m_checker_states[0]; | |
| ASSERT_EQ (merged_smap->get_state (merged_model->get_rvalue (p, nullptr), | |
| ext_state), | |
| TEST_STATE); | |
| /* Try canonicalizing. */ | |
| merged.m_region_model->canonicalize (); | |
| merged.validate (ext_state); | |
| /* Verify that the merged state still has the sm-state for "p". */ | |
| ASSERT_EQ (merged_smap->get_state (merged_model->get_rvalue (p, nullptr), | |
| ext_state), | |
| TEST_STATE); | |
| /* After canonicalization, we ought to have equality with the inputs. */ | |
| ASSERT_EQ (s0, merged); | |
| } | |
| /* Verify that program_states with different global-state in an sm-state | |
| can't be merged. */ | |
| static void | |
| test_program_state_merging_2 () | |
| { | |
| symbolic::node_manager node_mgr; | |
| auto &mgr = node_mgr.get_region_model_manager (); | |
| engine eng (node_mgr); | |
| program_point point (program_point::origin (mgr)); | |
| extrinsic_state ext_state (make_signal_state_machine (nullptr), &eng); | |
| const state_machine::state test_state_0 ("test state 0", 0); | |
| const state_machine::state test_state_1 ("test state 1", 1); | |
| const state_machine::state_t TEST_STATE_0 = &test_state_0; | |
| const state_machine::state_t TEST_STATE_1 = &test_state_1; | |
| program_state s0 (ext_state); | |
| { | |
| sm_state_map *smap0 = s0.m_checker_states[0]; | |
| smap0->set_global_state (TEST_STATE_0); | |
| ASSERT_EQ (smap0->get_global_state (), TEST_STATE_0); | |
| } | |
| program_state s1 (ext_state); | |
| { | |
| sm_state_map *smap1 = s1.m_checker_states[0]; | |
| smap1->set_global_state (TEST_STATE_1); | |
| ASSERT_EQ (smap1->get_global_state (), TEST_STATE_1); | |
| } | |
| ASSERT_NE (s0, s1); | |
| /* They ought to not be mergeable. */ | |
| program_state merged (ext_state); | |
| ASSERT_FALSE (s0.can_merge_with_p (s1, ext_state, point, &merged)); | |
| } | |
| /* Run all of the selftests within this file. */ | |
| void | |
| analyzer_program_state_cc_tests () | |
| { | |
| test_sm_state_map (); | |
| test_program_state_1 (); | |
| test_program_state_2 (); | |
| test_program_state_merging (); | |
| test_program_state_merging_2 (); | |
| } | |
| } // namespace selftest | |
| #endif /* CHECKING_P */ | |
| } // namespace ana | |
| #endif /* #if ENABLE_ANALYZER */ |