1/* Classes for representing the state of interest at a given path of analysis.
2   Copyright (C) 2019-2020 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
24namespace ana {
25
26/* Data shared by all program_state instances.  */
27
28class extrinsic_state
29{
30public:
31  extrinsic_state (auto_delete_vec <state_machine> &checkers)
32  : m_checkers (checkers)
33  {
34  }
35
36  const state_machine &get_sm (int idx) const
37  {
38    return *m_checkers[idx];
39  }
40
41  const char *get_name (int idx) const
42  {
43    return m_checkers[idx]->get_name ();
44  }
45
46  unsigned get_num_checkers () const { return m_checkers.length (); }
47
48  void dump_to_pp (pretty_printer *pp) const;
49  void dump_to_file (FILE *outf) const;
50  void dump () const;
51
52private:
53  /* The state machines.  */
54  auto_delete_vec <state_machine> &m_checkers;
55};
56
57} // namespace ana
58
59template <> struct default_hash_traits<svalue_id>
60: public pod_hash_traits<svalue_id>
61{
62  static const bool empty_zero_p = false;
63};
64
65template <>
66inline hashval_t
67pod_hash_traits<svalue_id>::hash (value_type v)
68{
69  return v.as_int ();
70}
71
72template <>
73inline bool
74pod_hash_traits<svalue_id>::equal (const value_type &existing,
75				   const value_type &candidate)
76{
77  return existing == candidate;
78}
79template <>
80inline void
81pod_hash_traits<svalue_id>::mark_deleted (value_type &v)
82{
83  v = svalue_id::from_int (-2);
84}
85template <>
86inline void
87pod_hash_traits<svalue_id>::mark_empty (value_type &v)
88{
89  v = svalue_id::null ();
90}
91template <>
92inline bool
93pod_hash_traits<svalue_id>::is_deleted (value_type v)
94{
95  return v.as_int () == -2;
96}
97template <>
98inline bool
99pod_hash_traits<svalue_id>::is_empty (value_type v)
100{
101  return v.null_p ();
102}
103
104namespace ana {
105
106/* Map from svalue_id to state machine state, also capturing the origin of
107   each state.  */
108
109class sm_state_map
110{
111public:
112  /* An entry in the hash_map.  */
113  struct entry_t
114  {
115    /* Default ctor needed by hash_map::empty.  */
116    entry_t ()
117    : m_state (0), m_origin (svalue_id::null ())
118    {
119    }
120
121    entry_t (state_machine::state_t state,
122	     svalue_id origin)
123    : m_state (state), m_origin (origin)
124    {}
125
126    bool operator== (const entry_t &other) const
127    {
128      return (m_state == other.m_state
129	      && m_origin == other.m_origin);
130    }
131    bool operator!= (const entry_t &other) const
132    {
133      return !(*this == other);
134    }
135
136    state_machine::state_t m_state;
137    svalue_id m_origin;
138  };
139  typedef hash_map <svalue_id, entry_t> map_t;
140  typedef map_t::iterator iterator_t;
141
142  sm_state_map ();
143
144  sm_state_map *clone () const;
145
146  sm_state_map *
147  clone_with_remapping (const one_way_svalue_id_map &id_map) const;
148
149  void print (const state_machine &sm, const region_model *model,
150	      pretty_printer *pp) const;
151  void dump (const state_machine &sm) const;
152
153  bool is_empty_p () const;
154
155  hashval_t hash () const;
156
157  bool operator== (const sm_state_map &other) const;
158  bool operator!= (const sm_state_map &other) const
159  {
160    return !(*this == other);
161  }
162
163  state_machine::state_t get_state (svalue_id sid) const;
164  svalue_id get_origin (svalue_id sid) const;
165
166  void set_state (region_model *model,
167		  svalue_id sid,
168		  state_machine::state_t state,
169		  svalue_id origin);
170  bool set_state (const equiv_class &ec,
171		  state_machine::state_t state,
172		  svalue_id origin);
173  bool impl_set_state (svalue_id sid,
174		       state_machine::state_t state,
175		       svalue_id origin);
176
177  void set_global_state (state_machine::state_t state);
178  state_machine::state_t get_global_state () const;
179
180  void purge_for_unknown_fncall (const exploded_graph &eg,
181				 const state_machine &sm,
182				 const gcall *call, tree fndecl,
183				 region_model *new_model,
184				 region_model_context *ctxt);
185
186  void remap_svalue_ids (const svalue_id_map &map);
187
188  int on_svalue_purge (const state_machine &sm,
189		       int sm_idx,
190		       svalue_id first_unused_sid,
191		       const svalue_id_map &map,
192		       impl_region_model_context *ctxt);
193
194  void on_inherited_svalue (svalue_id parent_sid,
195			    svalue_id child_sid);
196
197  void on_cast (svalue_id src_sid,
198		svalue_id dst_sid);
199
200  void on_unknown_change (svalue_id sid);
201
202  void validate (const state_machine &sm, int num_svalues) const;
203
204  iterator_t begin () const { return m_map.begin (); }
205  iterator_t end () const { return m_map.end (); }
206
207private:
208  map_t m_map;
209  state_machine::state_t m_global_state;
210};
211
212/* A class for representing the state of interest at a given path of
213   analysis.
214
215   Currently this is a combination of:
216   (a) a region_model, giving:
217      (a.1) a hierarchy of memory regions
218      (a.2) values for the regions
219      (a.3) inequalities between values
220   (b) sm_state_maps per state machine, giving a sparse mapping of
221       values to states.  */
222
223class program_state
224{
225public:
226  program_state (const extrinsic_state &ext_state);
227  program_state (const program_state &other);
228  program_state& operator= (const program_state &other);
229
230#if __cplusplus >= 201103
231  program_state (program_state &&other);
232  program_state& operator= (program_state &&other); // doesn't seem to be used
233#endif
234
235  ~program_state ();
236
237  hashval_t hash () const;
238  bool operator== (const program_state &other) const;
239  bool operator!= (const program_state &other) const
240  {
241    return !(*this == other);
242  }
243
244  void print (const extrinsic_state &ext_state,
245	      pretty_printer *pp) const;
246
247  void dump_to_pp (const extrinsic_state &ext_state, bool summarize,
248		   pretty_printer *pp) const;
249  void dump_to_file (const extrinsic_state &ext_state, bool summarize,
250		     FILE *outf) const;
251  void dump (const extrinsic_state &ext_state, bool summarize) const;
252
253  bool on_edge (exploded_graph &eg,
254		const exploded_node &enode,
255		const superedge *succ,
256		state_change *change);
257
258  program_state prune_for_point (exploded_graph &eg,
259				 const program_point &point,
260				 state_change *change) const;
261
262  void remap_svalue_ids (const svalue_id_map &map);
263
264  tree get_representative_tree (svalue_id sid) const;
265
266  bool can_purge_p (const extrinsic_state &ext_state,
267		    svalue_id sid)
268  {
269    /* Don't purge vars that have non-purgeable sm state, to avoid
270       generating false "leak" complaints.  */
271    int i;
272    sm_state_map *smap;
273    FOR_EACH_VEC_ELT (m_checker_states, i, smap)
274      {
275	const state_machine &sm = ext_state.get_sm (i);
276	if (!sm.can_purge_p (smap->get_state (sid)))
277	  return false;
278      }
279    return true;
280  }
281
282  bool can_merge_with_p (const program_state &other,
283			 const extrinsic_state &ext_state,
284			 program_state *out) const;
285
286  void validate (const extrinsic_state &ext_state) const;
287
288  /* TODO: lose the pointer here (const-correctness issues?).  */
289  region_model *m_region_model;
290  auto_delete_vec<sm_state_map> m_checker_states;
291
292  /* If false, then don't attempt to explore further states along this path.
293     For use in "handling" lvalues for tree codes we haven't yet
294     implemented.  */
295  bool m_valid;
296};
297
298/* An abstract base class for use with for_each_state_change.  */
299
300class state_change_visitor
301{
302public:
303  virtual ~state_change_visitor () {}
304
305  /* Return true for early exit, false to keep iterating.  */
306  virtual bool on_global_state_change (const state_machine &sm,
307				       state_machine::state_t src_sm_val,
308				       state_machine::state_t dst_sm_val) = 0;
309
310  /* Return true for early exit, false to keep iterating.  */
311  virtual bool on_state_change (const state_machine &sm,
312				state_machine::state_t src_sm_val,
313				state_machine::state_t dst_sm_val,
314				tree dst_rep,
315				svalue_id dst_origin_sid) = 0;
316};
317
318extern bool for_each_state_change (const program_state &src_state,
319				   const program_state &dst_state,
320				   const extrinsic_state &ext_state,
321				   state_change_visitor *visitor);
322
323/* A class for recording "interesting" state changes.
324   This is used for annotating edges in the GraphViz output of the
325   exploded_graph, and for recording sm-state-changes, so that
326   values that change aren't purged (to make it easier to generate
327   state_change_event instances in the diagnostic_path).  */
328
329class state_change
330{
331 public:
332  struct sm_change
333  {
334    sm_change (int sm_idx,
335	       svalue_id new_sid,
336	       state_machine::state_t old_state,
337	       state_machine::state_t new_state)
338    : m_sm_idx (sm_idx),
339      m_new_sid (new_sid),
340      m_old_state (old_state), m_new_state (new_state)
341    {}
342
343    const state_machine &get_sm (const extrinsic_state &ext_state) const
344    {
345      return ext_state.get_sm (m_sm_idx);
346    }
347
348    void dump (pretty_printer *pp, const extrinsic_state &ext_state) const;
349
350    void remap_svalue_ids (const svalue_id_map &map);
351    int on_svalue_purge (svalue_id first_unused_sid);
352
353    void validate (const program_state &new_state,
354		   const extrinsic_state &ext_state) const;
355
356    int m_sm_idx;
357    svalue_id m_new_sid;
358    state_machine::state_t m_old_state;
359    state_machine::state_t m_new_state;
360  };
361
362  state_change ();
363  state_change (const state_change &other);
364
365  void add_sm_change (int sm_idx,
366		      svalue_id new_sid,
367		      state_machine::state_t old_state,
368		      state_machine::state_t new_state);
369
370  bool affects_p (svalue_id sid) const;
371
372  void dump (pretty_printer *pp, const extrinsic_state &ext_state) const;
373  void dump (const extrinsic_state &ext_state) const;
374
375  void remap_svalue_ids (const svalue_id_map &map);
376  int on_svalue_purge (svalue_id first_unused_sid);
377
378  void validate (const program_state &new_state,
379		 const extrinsic_state &ext_state) const;
380
381 private:
382  auto_vec<sm_change> m_sm_changes;
383};
384
385} // namespace ana
386
387#endif /* GCC_ANALYZER_PROGRAM_STATE_H */
388