Line data Source code
1 : /* Classes for representing the state of interest at a given path of analysis.
2 : Copyright (C) 2019-2026 Free Software Foundation, Inc.
3 : Contributed by David Malcolm <dmalcolm@redhat.com>.
4 :
5 : This file is part of GCC.
6 :
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)
10 : any later version.
11 :
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.
16 :
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/>. */
20 :
21 : #ifndef GCC_ANALYZER_PROGRAM_STATE_H
22 : #define GCC_ANALYZER_PROGRAM_STATE_H
23 :
24 : #include "text-art/widget.h"
25 : #include "text-art/tree-widget.h"
26 :
27 : #include "analyzer/store.h"
28 :
29 : namespace ana {
30 :
31 : /* Data shared by all program_state instances. */
32 :
33 3593 : class extrinsic_state
34 : {
35 : public:
36 3581 : extrinsic_state (std::vector<std::unique_ptr<state_machine>> &&checkers,
37 : engine *eng,
38 : logger *logger = nullptr)
39 3581 : : m_checkers (std::move (checkers)),
40 3581 : m_logger (logger),
41 3581 : m_engine (eng)
42 : {
43 : }
44 :
45 : // For use in selftests that use just one state machine
46 12 : extrinsic_state (std::unique_ptr<state_machine> sm,
47 : engine *eng,
48 : logger *logger = nullptr)
49 12 : : m_logger (logger),
50 12 : m_engine (eng)
51 : {
52 12 : m_checkers.push_back (std::move (sm));
53 : }
54 :
55 8114030 : const state_machine &get_sm (int idx) const
56 : {
57 6924892 : return *m_checkers[idx];
58 : }
59 :
60 9 : const char *get_name (int idx) const
61 : {
62 9 : return m_checkers[idx]->get_name ();
63 : }
64 :
65 2373506 : unsigned get_num_checkers () const { return m_checkers.size (); }
66 :
67 433757 : logger *get_logger () const { return m_logger; }
68 :
69 : void dump_to_logger (logger &) const;
70 : void dump () const;
71 :
72 : std::unique_ptr<text_art::tree_widget>
73 : make_dump_widget (symbolic::node_dump_state &nds) const;
74 :
75 : std::unique_ptr<json::object> to_json () const;
76 :
77 438480 : engine *get_engine () const { return m_engine; }
78 :
79 : symbolic::node_manager &
80 : get_node_manager () const;
81 :
82 : region_model_manager *get_model_manager () const;
83 :
84 : bool get_sm_idx_by_name (const char *name, unsigned *out) const;
85 :
86 : private:
87 : /* The state machines. */
88 : std::vector<std::unique_ptr<state_machine>> m_checkers;
89 :
90 : logger *m_logger;
91 : engine *m_engine;
92 : };
93 :
94 : /* Map from svalue * to state machine state, also capturing the origin of
95 : each state. */
96 :
97 : class sm_state_map
98 : {
99 : public:
100 : /* An entry in the hash_map. */
101 : struct entry_t
102 : {
103 : /* Default ctor needed by hash_map::empty. */
104 : entry_t ()
105 : : m_state (0), m_origin (nullptr)
106 : {
107 : }
108 :
109 84108 : entry_t (state_machine::state_t state,
110 : const svalue *origin)
111 84108 : : m_state (state), m_origin (origin)
112 : {}
113 :
114 77218 : bool operator== (const entry_t &other) const
115 : {
116 77218 : return (m_state == other.m_state
117 70496 : && m_origin == other.m_origin);
118 : }
119 77218 : bool operator!= (const entry_t &other) const
120 : {
121 152107 : return !(*this == other);
122 : }
123 :
124 : static int cmp (const entry_t &entry_a, const entry_t &entry_b);
125 :
126 : state_machine::state_t m_state;
127 : const svalue *m_origin;
128 : };
129 : typedef hash_map <const svalue *, entry_t> map_t;
130 : typedef map_t::iterator iterator_t;
131 :
132 : sm_state_map (const state_machine &sm);
133 :
134 : sm_state_map *clone () const;
135 :
136 : void print (const region_model *model,
137 : bool simple, bool multiline,
138 : pretty_printer *pp) const;
139 : void dump (bool simple) const;
140 :
141 : std::unique_ptr<json::object> to_json () const;
142 :
143 : std::unique_ptr<text_art::tree_widget>
144 : make_dump_widget (symbolic::node_dump_state &nds,
145 : const region_model *model = nullptr) const;
146 : void dump () const;
147 :
148 : bool is_empty_p () const;
149 :
150 : hashval_t hash () const;
151 :
152 : bool operator== (const sm_state_map &other) const;
153 4 : bool operator!= (const sm_state_map &other) const
154 : {
155 4 : return !(*this == other);
156 : }
157 :
158 : state_machine::state_t get_state (const svalue *sval,
159 : const extrinsic_state &ext_state) const;
160 : const svalue *get_origin (const svalue *sval,
161 : const extrinsic_state &ext_state) const;
162 :
163 : void set_state (region_model *model,
164 : const svalue *sval,
165 : state_machine::state_t state,
166 : const svalue *origin,
167 : const extrinsic_state &ext_state);
168 : bool set_state (const equiv_class &ec,
169 : state_machine::state_t state,
170 : const svalue *origin,
171 : const extrinsic_state &ext_state);
172 : bool impl_set_state (const svalue *sval,
173 : state_machine::state_t state,
174 : const svalue *origin,
175 : const extrinsic_state &ext_state);
176 : void clear_any_state (const svalue *sval);
177 : void clear_all_per_svalue_state ();
178 :
179 : void set_global_state (state_machine::state_t state);
180 : state_machine::state_t get_global_state () const;
181 :
182 : void on_svalue_leak (const svalue *sval,
183 : impl_region_model_context *ctxt);
184 : void on_liveness_change (symbolic::liveness_context &liveness_ctxt,
185 : const extrinsic_state &ext_state,
186 : impl_region_model_context *ctxt);
187 :
188 : void on_unknown_change (const symbolic::value_node &val,
189 : bool is_mutable,
190 : const extrinsic_state &ext_state);
191 :
192 : void purge_state_involving (const symbolic::node &node,
193 : const extrinsic_state &ext_state);
194 :
195 1079732 : iterator_t begin () const { return m_map.begin (); }
196 1273944 : iterator_t end () const { return m_map.end (); }
197 643234 : size_t elements () const { return m_map.elements (); }
198 :
199 : static int cmp (const sm_state_map &smap_a, const sm_state_map &smap_b);
200 :
201 : static const svalue *
202 : canonicalize_svalue (const svalue *sval, const extrinsic_state &ext_state);
203 :
204 : bool replay_call_summary (call_summary_replay &r,
205 : const sm_state_map &summary);
206 :
207 : bool can_merge_with_p (const sm_state_map &other,
208 : const state_machine &sm,
209 : const extrinsic_state &ext_state,
210 : sm_state_map **out) const;
211 :
212 : void validate (const extrinsic_state &ext_state) const;
213 :
214 : private:
215 : state_machine::state_t
216 : get_any_inherited_state_of_bit_vector (const symbolic::bit_vector &bv,
217 : const extrinsic_state &ext_state,
218 : region_model_manager &rmm) const;
219 :
220 : const state_machine &m_sm;
221 : map_t m_map;
222 : state_machine::state_t m_global_state;
223 : std::map<const symbolic::unfoldable_bit_contents *,
224 : state_machine::state_t> m_map_ubc_to_state;
225 : };
226 :
227 : /* A class for representing the state of interest at a given path of
228 : analysis.
229 :
230 : Currently this is a combination of:
231 : (a) a region_model, giving:
232 : (a.1) a hierarchy of memory regions
233 : (a.2) values for the regions
234 : (a.3) inequalities between values
235 : (b) sm_state_maps per state machine, giving a sparse mapping of
236 : values to states. */
237 :
238 : class program_state
239 : {
240 : public:
241 : program_state (const extrinsic_state &ext_state);
242 : program_state (const program_state &other);
243 : program_state& operator= (const program_state &other);
244 : program_state (program_state &&other);
245 : program_state& operator= (program_state &&other);
246 : ~program_state ();
247 :
248 : hashval_t hash () const;
249 : bool operator== (const program_state &other) const;
250 28613 : bool operator!= (const program_state &other) const
251 : {
252 28613 : return !(*this == other);
253 : }
254 :
255 : void print (const extrinsic_state &ext_state,
256 : pretty_printer *pp) const;
257 :
258 : void dump_to_logger (logger &, const char *label = nullptr) const;
259 : void dump () const;
260 :
261 : std::unique_ptr<diagnostics::digraphs::digraph>
262 : make_diagnostic_state_graph (const extrinsic_state &ext_state) const;
263 :
264 : void
265 : dump_sarif (const extrinsic_state &ext_state) const;
266 :
267 : void
268 : dump_dot (const extrinsic_state &ext_state) const;
269 :
270 : std::unique_ptr<json::object>
271 : to_json (const extrinsic_state &ext_state) const;
272 :
273 : std::unique_ptr<text_art::tree_widget>
274 : make_dump_widget (symbolic::node_dump_state &nds,
275 : const char *label = nullptr) const;
276 :
277 : void push_frame (const extrinsic_state &ext_state, const function &fun);
278 : const function * get_current_function () const;
279 :
280 : program_state prune_for_point (exploded_graph &eg,
281 : const program_point &point,
282 : exploded_node *enode_for_diag,
283 : uncertainty_t *uncertainty) const;
284 :
285 : tree get_representative_tree (const svalue *sval) const;
286 :
287 482730 : bool can_purge_p (const extrinsic_state &ext_state,
288 : const svalue *sval) const
289 : {
290 : /* Don't purge vars that have non-purgeable sm state, to avoid
291 : generating false "leak" complaints. */
292 482730 : int i;
293 482730 : sm_state_map *smap;
294 3674539 : FOR_EACH_VEC_ELT (m_checker_states, i, smap)
295 : {
296 3218950 : const state_machine &sm = ext_state.get_sm (i);
297 3218950 : if (!sm.can_purge_p (smap->get_state (sval, ext_state)))
298 : return false;
299 : }
300 : return true;
301 : }
302 :
303 : bool can_purge_base_region_p (const extrinsic_state &ext_state,
304 : const region *base_reg) const;
305 :
306 : bool can_merge_with_p (const program_state &other,
307 : const extrinsic_state &ext_state,
308 : const program_point &point,
309 : program_state *out) const;
310 :
311 : void validate (const extrinsic_state &ext_state) const;
312 :
313 : static void detect_leaks (const program_state &src_state,
314 : const program_state &dest_state,
315 : const svalue *extra_sval,
316 : const extrinsic_state &ext_state,
317 : region_model_context *ctxt);
318 :
319 : bool replay_call_summary (call_summary_replay &r,
320 : const program_state &summary);
321 :
322 : void impl_call_analyzer_dump_state (const gcall &call,
323 : const extrinsic_state &ext_state,
324 : region_model_context *ctxt);
325 :
326 : /* TODO: lose the pointer here (const-correctness issues?). */
327 : region_model *m_region_model;
328 : auto_delete_vec<sm_state_map> m_checker_states;
329 :
330 : /* If false, then don't attempt to explore further states along this path.
331 : For use in "handling" lvalues for tree codes we haven't yet
332 : implemented. */
333 : bool m_valid;
334 : };
335 :
336 : /* An abstract base class for use with for_each_state_change. */
337 :
338 44029 : class state_change_visitor
339 : {
340 : public:
341 44029 : virtual ~state_change_visitor () {}
342 :
343 : /* Return true for early exit, false to keep iterating. */
344 : virtual bool on_global_state_change (const state_machine &sm,
345 : state_machine::state_t src_sm_val,
346 : state_machine::state_t dst_sm_val) = 0;
347 :
348 : /* Return true for early exit, false to keep iterating. */
349 : virtual bool on_state_change (const state_machine &sm,
350 : state_machine::state_t src_sm_val,
351 : state_machine::state_t dst_sm_val,
352 : const svalue *dst_sval,
353 : const svalue *dst_origin_sval) = 0;
354 : };
355 :
356 : extern bool for_each_state_change (const program_state &src_state,
357 : const program_state &dst_state,
358 : const extrinsic_state &ext_state,
359 : state_change_visitor *visitor);
360 :
361 : } // namespace ana
362 :
363 : #endif /* GCC_ANALYZER_PROGRAM_STATE_H */
|