gcc/analyzer/program-state.h

   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
   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 namespace ana {
  25
  26 /* Data shared by all program_state instances.  */
  27
  28 class extrinsic_state
  29 {
  30 public:
  31   extrinsic_state (auto_delete_vec <state_machine> &checkers,
  32                    logger *logger = NULL,
  33                    engine *eng = NULL)
  34   : m_checkers (checkers), m_logger (logger), m_engine (eng)
  35   {
  36   }
  37
  38   const state_machine &get_sm (int idx) const
  39   {
  40     return *m_checkers[idx];
  41   }
  42
  43   const char *get_name (int idx) const
  44   {
  45     return m_checkers[idx]->get_name ();
  46   }
  47
  48   unsigned get_num_checkers () const { return m_checkers.length (); }
  49
  50   logger *get_logger () const { return m_logger; }
  51
  52   void dump_to_pp (pretty_printer *pp) const;
  53   void dump_to_file (FILE *outf) const;
  54   void dump () const;
  55
  56   json::object *to_json () const;
  57
  58   engine *get_engine () const { return m_engine; }
  59   region_model_manager *get_model_manager () const;
  60
  61 private:
  62   /* The state machines.  */
  63   auto_delete_vec <state_machine> &m_checkers;
  64
  65   logger *m_logger;
  66   engine *m_engine;
  67 };
  68
  69 /* Map from svalue * to state machine state, also capturing the origin of
  70    each state.  */
  71
  72 class sm_state_map
  73 {
  74 public:
  75   /* An entry in the hash_map.  */
  76   struct entry_t
  77   {
  78     /* Default ctor needed by hash_map::empty.  */
  79     entry_t ()
  80     : m_state (0), m_origin (NULL)
  81     {
  82     }
  83
  84     entry_t (state_machine::state_t state,
  85              const svalue *origin)
  86     : m_state (state), m_origin (origin)
  87     {}
  88
  89     bool operator== (const entry_t &other) const
  90     {
  91       return (m_state == other.m_state
  92               && m_origin == other.m_origin);
  93     }
  94     bool operator!= (const entry_t &other) const
  95     {
  96       return !(*this == other);
  97     }
  98
  99     state_machine::state_t m_state;
 100     const svalue *m_origin;
 101   };
 102   typedef hash_map <const svalue *, entry_t> map_t;
 103   typedef map_t::iterator iterator_t;
 104
 105   sm_state_map (const state_machine &sm, int m_sm_idx);
 106
 107   sm_state_map *clone () const;
 108
 109   void print (const region_model *model,
 110               bool simple, bool multiline,
 111               pretty_printer *pp) const;
 112   void dump (bool simple) const;
 113
 114   json::object *to_json () const;
 115
 116   bool is_empty_p () const;
 117
 118   hashval_t hash () const;
 119
 120   bool operator== (const sm_state_map &other) const;
 121   bool operator!= (const sm_state_map &other) const
 122   {
 123     return !(*this == other);
 124   }
 125
 126   state_machine::state_t get_state (const svalue *sval,
 127                                     const extrinsic_state &ext_state) const;
 128   const svalue *get_origin (const svalue *sval,
 129                             const extrinsic_state &ext_state) const;
 130
 131   void set_state (region_model *model,
 132                   const svalue *sval,
 133                   state_machine::state_t state,
 134                   const svalue *origin,
 135                   const extrinsic_state &ext_state);
 136   bool set_state (const equiv_class &ec,
 137                   state_machine::state_t state,
 138                   const svalue *origin,
 139                   const extrinsic_state &ext_state);
 140   bool impl_set_state (const svalue *sval,
 141                        state_machine::state_t state,
 142                        const svalue *origin,
 143                        const extrinsic_state &ext_state);
 144
 145   void set_global_state (state_machine::state_t state);
 146   state_machine::state_t get_global_state () const;
 147
 148   void on_svalue_leak (const svalue *sval,
 149                        impl_region_model_context *ctxt);
 150   void on_liveness_change (const svalue_set &live_svalues,
 151                            const region_model *model,
 152                            impl_region_model_context *ctxt);
 153
 154   void on_unknown_change (const svalue *sval,
 155                           bool is_mutable,
 156                           const extrinsic_state &ext_state);
 157
 158   iterator_t begin () const { return m_map.begin (); }
 159   iterator_t end () const { return m_map.end (); }
 160
 161   static const svalue *
 162   canonicalize_svalue (const svalue *sval, const extrinsic_state &ext_state);
 163
 164 private:
 165   const state_machine &m_sm;
 166   int m_sm_idx;
 167   map_t m_map;
 168   state_machine::state_t m_global_state;
 169 };
 170
 171 /* A class for representing the state of interest at a given path of
 172    analysis.
 173
 174    Currently this is a combination of:
 175    (a) a region_model, giving:
 176       (a.1) a hierarchy of memory regions
 177       (a.2) values for the regions
 178       (a.3) inequalities between values
 179    (b) sm_state_maps per state machine, giving a sparse mapping of
 180        values to states.  */
 181
 182 class program_state
 183 {
 184 public:
 185   program_state (const extrinsic_state &ext_state);
 186   program_state (const program_state &other);
 187   program_state& operator= (const program_state &other);
 188
 189 #if __cplusplus >= 201103
 190   program_state (program_state &&other);
 191 #endif
 192
 193   ~program_state ();
 194
 195   hashval_t hash () const;
 196   bool operator== (const program_state &other) const;
 197   bool operator!= (const program_state &other) const
 198   {
 199     return !(*this == other);
 200   }
 201
 202   void print (const extrinsic_state &ext_state,
 203               pretty_printer *pp) const;
 204
 205   void dump_to_pp (const extrinsic_state &ext_state, bool simple,
 206                    bool multiline, pretty_printer *pp) const;
 207   void dump_to_file (const extrinsic_state &ext_state, bool simple,
 208                      bool multiline, FILE *outf) const;
 209   void dump (const extrinsic_state &ext_state, bool simple) const;
 210
 211   json::object *to_json (const extrinsic_state &ext_state) const;
 212
 213   void push_frame (const extrinsic_state &ext_state, function *fun);
 214   function * get_current_function () const;
 215
 216   bool on_edge (exploded_graph &eg,
 217                 const exploded_node &enode,
 218                 const superedge *succ);
 219
 220   program_state prune_for_point (exploded_graph &eg,
 221                                  const program_point &point,
 222                                  const exploded_node *enode_for_diag) const;
 223
 224   tree get_representative_tree (const svalue *sval) const;
 225
 226   bool can_purge_p (const extrinsic_state &ext_state,
 227                     const svalue *sval)
 228   {
 229     /* Don't purge vars that have non-purgeable sm state, to avoid
 230        generating false "leak" complaints.  */
 231     int i;
 232     sm_state_map *smap;
 233     FOR_EACH_VEC_ELT (m_checker_states, i, smap)
 234       {
 235         const state_machine &sm = ext_state.get_sm (i);
 236         if (!sm.can_purge_p (smap->get_state (sval, ext_state)))
 237           return false;
 238       }
 239     return true;
 240   }
 241
 242   bool can_merge_with_p (const program_state &other,
 243                          const program_point &point,
 244                          program_state *out) const;
 245
 246   void validate (const extrinsic_state &ext_state) const;
 247
 248   static void detect_leaks (const program_state &src_state,
 249                             const program_state &dest_state,
 250                             const svalue *extra_sval,
 251                             const extrinsic_state &ext_state,
 252                             region_model_context *ctxt);
 253
 254   /* TODO: lose the pointer here (const-correctness issues?).  */
 255   region_model *m_region_model;
 256   auto_delete_vec<sm_state_map> m_checker_states;
 257
 258   /* If false, then don't attempt to explore further states along this path.
 259      For use in "handling" lvalues for tree codes we haven't yet
 260      implemented.  */
 261   bool m_valid;
 262 };
 263
 264 /* An abstract base class for use with for_each_state_change.  */
 265
 266 class state_change_visitor
 267 {
 268 public:
 269   virtual ~state_change_visitor () {}
 270
 271   /* Return true for early exit, false to keep iterating.  */
 272   virtual bool on_global_state_change (const state_machine &sm,
 273                                        state_machine::state_t src_sm_val,
 274                                        state_machine::state_t dst_sm_val) = 0;
 275
 276   /* Return true for early exit, false to keep iterating.  */
 277   virtual bool on_state_change (const state_machine &sm,
 278                                 state_machine::state_t src_sm_val,
 279                                 state_machine::state_t dst_sm_val,
 280                                 const svalue *dst_sval,
 281                                 const svalue *dst_origin_sval) = 0;
 282 };
 283
 284 extern bool for_each_state_change (const program_state &src_state,
 285                                     const program_state &dst_state,
 286                                     const extrinsic_state &ext_state,
 287                                     state_change_visitor *visitor);
 288
 289 } // namespace ana
 290
 291 #endif /* GCC_ANALYZER_PROGRAM_STATE_H */