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