gcc/analyzer/program-state.h

   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
   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 xml { class document; }
  30
  31 namespace ana {
  32
  33 /* Data shared by all program_state instances.  */
  34
  35 class extrinsic_state
  36 {
  37 public:
  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
  82 private:
  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
  93 class sm_state_map
  94 {
  95 public:
  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
 208 private:
 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
 225 class program_state
 226 {
 227 public:
 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
 340 class state_change_visitor
 341 {
 342 public:
 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
 358 extern 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 */