gcc/analyzer/region-model.h

   1 /* Classes for modeling the state of memory.
   2    Copyright (C) 2019-2022 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_REGION_MODEL_H
  22 #define GCC_ANALYZER_REGION_MODEL_H
  23
  24 /* Implementation of the region-based ternary model described in:
  25      "A Memory Model for Static Analysis of C Programs"
  26       (Zhongxing Xu, Ted Kremenek, and Jian Zhang)
  27      http://lcs.ios.ac.cn/~xuzb/canalyze/memmodel.pdf  */
  28
  29 #include "selftest.h"
  30 #include "analyzer/svalue.h"
  31 #include "analyzer/region.h"
  32 #include "analyzer/known-function-manager.h"
  33 #include "analyzer/region-model-manager.h"
  34 #include "analyzer/pending-diagnostic.h"
  35
  36 using namespace ana;
  37
  38 namespace inchash
  39 {
  40   extern void add_path_var (path_var pv, hash &hstate);
  41 } // namespace inchash
  42
  43 namespace ana {
  44
  45 template <typename T>
  46 class one_way_id_map
  47 {
  48  public:
  49   one_way_id_map (int num_ids);
  50   void put (T src, T dst);
  51   T get_dst_for_src (T src) const;
  52   void dump_to_pp (pretty_printer *pp) const;
  53   void dump () const;
  54   void update (T *) const;
  55
  56  private:
  57   auto_vec<T> m_src_to_dst;
  58  };
  59
  60 /* class one_way_id_map.  */
  61
  62 /* one_way_id_map's ctor, which populates the map with dummy null values.  */
  63
  64 template <typename T>
  65 inline one_way_id_map<T>::one_way_id_map (int num_svalues)
  66 : m_src_to_dst (num_svalues)
  67 {
  68   for (int i = 0; i < num_svalues; i++)
  69     m_src_to_dst.quick_push (T::null ());
  70 }
  71
  72 /* Record that SRC is to be mapped to DST.  */
  73
  74 template <typename T>
  75 inline void
  76 one_way_id_map<T>::put (T src, T dst)
  77 {
  78   m_src_to_dst[src.as_int ()] = dst;
  79 }
  80
  81 /* Get the new value for SRC within the map.  */
  82
  83 template <typename T>
  84 inline T
  85 one_way_id_map<T>::get_dst_for_src (T src) const
  86 {
  87   if (src.null_p ())
  88     return src;
  89   return m_src_to_dst[src.as_int ()];
  90 }
  91
  92 /* Dump this map to PP.  */
  93
  94 template <typename T>
  95 inline void
  96 one_way_id_map<T>::dump_to_pp (pretty_printer *pp) const
  97 {
  98   pp_string (pp, "src to dst: {");
  99   unsigned i;
 100   T *dst;
 101   FOR_EACH_VEC_ELT (m_src_to_dst, i, dst)
 102     {
 103       if (i > 0)
 104         pp_string (pp, ", ");
 105       T src (T::from_int (i));
 106       src.print (pp);
 107       pp_string (pp, " -> ");
 108       dst->print (pp);
 109     }
 110   pp_string (pp, "}");
 111   pp_newline (pp);
 112 }
 113
 114 /* Dump this map to stderr.  */
 115
 116 template <typename T>
 117 DEBUG_FUNCTION inline void
 118 one_way_id_map<T>::dump () const
 119 {
 120   pretty_printer pp;
 121   pp.buffer->stream = stderr;
 122   dump_to_pp (&pp);
 123   pp_flush (&pp);
 124 }
 125
 126 /* Update *ID from the old value to its new value in this map.  */
 127
 128 template <typename T>
 129 inline void
 130 one_way_id_map<T>::update (T *id) const
 131 {
 132   *id = get_dst_for_src (*id);
 133 }
 134
 135 /* A mapping from region to svalue for use when tracking state.  */
 136
 137 class region_to_value_map
 138 {
 139 public:
 140   typedef hash_map<const region *, const svalue *> hash_map_t;
 141   typedef hash_map_t::iterator iterator;
 142
 143   region_to_value_map () : m_hash_map () {}
 144   region_to_value_map (const region_to_value_map &other)
 145   : m_hash_map (other.m_hash_map) {}
 146   region_to_value_map &operator= (const region_to_value_map &other);
 147
 148   bool operator== (const region_to_value_map &other) const;
 149   bool operator!= (const region_to_value_map &other) const
 150   {
 151     return !(*this == other);
 152   }
 153
 154   iterator begin () const { return m_hash_map.begin (); }
 155   iterator end () const { return m_hash_map.end (); }
 156
 157   const svalue * const *get (const region *reg) const
 158   {
 159     return const_cast <hash_map_t &> (m_hash_map).get (reg);
 160   }
 161   void put (const region *reg, const svalue *sval)
 162   {
 163     m_hash_map.put (reg, sval);
 164   }
 165   void remove (const region *reg)
 166   {
 167     m_hash_map.remove (reg);
 168   }
 169
 170   bool is_empty () const { return m_hash_map.is_empty (); }
 171
 172   void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
 173   void dump (bool simple) const;
 174
 175   bool can_merge_with_p (const region_to_value_map &other,
 176                          region_to_value_map *out) const;
 177
 178   void purge_state_involving (const svalue *sval);
 179
 180 private:
 181   hash_map_t m_hash_map;
 182 };
 183
 184 /* Various operations delete information from a region_model.
 185
 186    This struct tracks how many of each kind of entity were purged (e.g.
 187    for selftests, and for debugging).  */
 188
 189 struct purge_stats
 190 {
 191   purge_stats ()
 192   : m_num_svalues (0),
 193     m_num_regions (0),
 194     m_num_equiv_classes (0),
 195     m_num_constraints (0),
 196     m_num_bounded_ranges_constraints (0),
 197     m_num_client_items (0)
 198   {}
 199
 200   int m_num_svalues;
 201   int m_num_regions;
 202   int m_num_equiv_classes;
 203   int m_num_constraints;
 204   int m_num_bounded_ranges_constraints;
 205   int m_num_client_items;
 206 };
 207
 208 /* A base class for visiting regions and svalues, with do-nothing
 209    base implementations of the per-subclass vfuncs.  */
 210
 211 class visitor
 212 {
 213 public:
 214   virtual void visit_region_svalue (const region_svalue *) {}
 215   virtual void visit_constant_svalue (const constant_svalue *) {}
 216   virtual void visit_unknown_svalue (const unknown_svalue *) {}
 217   virtual void visit_poisoned_svalue (const poisoned_svalue *) {}
 218   virtual void visit_setjmp_svalue (const setjmp_svalue *) {}
 219   virtual void visit_initial_svalue (const initial_svalue *) {}
 220   virtual void visit_unaryop_svalue (const unaryop_svalue *) {}
 221   virtual void visit_binop_svalue (const binop_svalue *) {}
 222   virtual void visit_sub_svalue (const sub_svalue *) {}
 223   virtual void visit_repeated_svalue (const repeated_svalue *) {}
 224   virtual void visit_bits_within_svalue (const bits_within_svalue *) {}
 225   virtual void visit_unmergeable_svalue (const unmergeable_svalue *) {}
 226   virtual void visit_placeholder_svalue (const placeholder_svalue *) {}
 227   virtual void visit_widening_svalue (const widening_svalue *) {}
 228   virtual void visit_compound_svalue (const compound_svalue *) {}
 229   virtual void visit_conjured_svalue (const conjured_svalue *) {}
 230   virtual void visit_asm_output_svalue (const asm_output_svalue *) {}
 231   virtual void visit_const_fn_result_svalue (const const_fn_result_svalue *) {}
 232
 233   virtual void visit_region (const region *) {}
 234 };
 235
 236 struct append_regions_cb_data;
 237
 238 /* Helper class for handling calls to functions with known behavior.
 239    Implemented in region-model-impl-calls.c.  */
 240
 241 class call_details
 242 {
 243 public:
 244   call_details (const gcall *call, region_model *model,
 245                 region_model_context *ctxt);
 246
 247   region_model *get_model () const { return m_model; }
 248   region_model_manager *get_manager () const;
 249   region_model_context *get_ctxt () const { return m_ctxt; }
 250   logger *get_logger () const;
 251
 252   uncertainty_t *get_uncertainty () const;
 253   tree get_lhs_type () const { return m_lhs_type; }
 254   const region *get_lhs_region () const { return m_lhs_region; }
 255
 256   bool maybe_set_lhs (const svalue *result) const;
 257
 258   unsigned num_args () const;
 259   bool arg_is_pointer_p (unsigned idx) const
 260   {
 261     return POINTER_TYPE_P (get_arg_type (idx));
 262   }
 263   bool arg_is_size_p (unsigned idx) const;
 264
 265   const gcall *get_call_stmt () const { return m_call; }
 266   location_t get_location () const;
 267
 268   tree get_arg_tree (unsigned idx) const;
 269   tree get_arg_type (unsigned idx) const;
 270   const svalue *get_arg_svalue (unsigned idx) const;
 271   const char *get_arg_string_literal (unsigned idx) const;
 272
 273   tree get_fndecl_for_call () const;
 274
 275   void dump_to_pp (pretty_printer *pp, bool simple) const;
 276   void dump (bool simple) const;
 277
 278   const svalue *get_or_create_conjured_svalue (const region *) const;
 279
 280 private:
 281   const gcall *m_call;
 282   region_model *m_model;
 283   region_model_context *m_ctxt;
 284   tree m_lhs_type;
 285   const region *m_lhs_region;
 286 };
 287
 288 /* A region_model encapsulates a representation of the state of memory, with
 289    a tree of regions, along with their associated values.
 290    The representation is graph-like because values can be pointers to
 291    regions.
 292    It also stores:
 293    - a constraint_manager, capturing relationships between the values, and
 294    - dynamic extents, mapping dynamically-allocated regions to svalues (their
 295    capacities).  */
 296
 297 class region_model
 298 {
 299  public:
 300   typedef region_to_value_map dynamic_extents_t;
 301
 302   region_model (region_model_manager *mgr);
 303   region_model (const region_model &other);
 304   ~region_model ();
 305   region_model &operator= (const region_model &other);
 306
 307   bool operator== (const region_model &other) const;
 308   bool operator!= (const region_model &other) const
 309   {
 310     return !(*this == other);
 311   }
 312
 313   hashval_t hash () const;
 314
 315   void print (pretty_printer *pp) const;
 316
 317   void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
 318   void dump (FILE *fp, bool simple, bool multiline) const;
 319   void dump (bool simple) const;
 320
 321   void debug () const;
 322
 323   void validate () const;
 324
 325   void canonicalize ();
 326   bool canonicalized_p () const;
 327
 328   void
 329   on_stmt_pre (const gimple *stmt,
 330                bool *out_unknown_side_effects,
 331                region_model_context *ctxt);
 332
 333   void on_assignment (const gassign *stmt, region_model_context *ctxt);
 334   const svalue *get_gassign_result (const gassign *assign,
 335                                     region_model_context *ctxt);
 336   void on_asm_stmt (const gasm *asm_stmt, region_model_context *ctxt);
 337   bool on_call_pre (const gcall *stmt, region_model_context *ctxt);
 338   void on_call_post (const gcall *stmt,
 339                      bool unknown_side_effects,
 340                      region_model_context *ctxt);
 341
 342   void purge_state_involving (const svalue *sval, region_model_context *ctxt);
 343
 344   void impl_deallocation_call (const call_details &cd);
 345
 346   const svalue *maybe_get_copy_bounds (const region *src_reg,
 347                                        const svalue *num_bytes_sval);
 348   void update_for_int_cst_return (const call_details &cd,
 349                                   int retval,
 350                                   bool unmergeable);
 351   void update_for_zero_return (const call_details &cd,
 352                                bool unmergeable);
 353   void update_for_nonzero_return (const call_details &cd);
 354
 355   void handle_unrecognized_call (const gcall *call,
 356                                  region_model_context *ctxt);
 357   void get_reachable_svalues (svalue_set *out,
 358                               const svalue *extra_sval,
 359                               const uncertainty_t *uncertainty);
 360
 361   void on_return (const greturn *stmt, region_model_context *ctxt);
 362   void on_setjmp (const gcall *stmt, const exploded_node *enode,
 363                   region_model_context *ctxt);
 364   void on_longjmp (const gcall *longjmp_call, const gcall *setjmp_call,
 365                    int setjmp_stack_depth, region_model_context *ctxt);
 366
 367   void update_for_phis (const supernode *snode,
 368                         const cfg_superedge *last_cfg_superedge,
 369                         region_model_context *ctxt);
 370
 371   void handle_phi (const gphi *phi, tree lhs, tree rhs,
 372                    const region_model &old_state,
 373                    region_model_context *ctxt);
 374
 375   bool maybe_update_for_edge (const superedge &edge,
 376                               const gimple *last_stmt,
 377                               region_model_context *ctxt,
 378                               rejected_constraint **out);
 379
 380   void update_for_gcall (const gcall *call_stmt,
 381                          region_model_context *ctxt,
 382                          function *callee = NULL);
 383
 384   void update_for_return_gcall (const gcall *call_stmt,
 385                                 region_model_context *ctxt);
 386
 387   const region *push_frame (function *fun, const vec<const svalue *> *arg_sids,
 388                             region_model_context *ctxt);
 389   const frame_region *get_current_frame () const { return m_current_frame; }
 390   function * get_current_function () const;
 391   void pop_frame (tree result_lvalue,
 392                   const svalue **out_result,
 393                   region_model_context *ctxt);
 394   int get_stack_depth () const;
 395   const frame_region *get_frame_at_index (int index) const;
 396
 397   const region *get_lvalue (path_var pv, region_model_context *ctxt) const;
 398   const region *get_lvalue (tree expr, region_model_context *ctxt) const;
 399   const svalue *get_rvalue (path_var pv, region_model_context *ctxt) const;
 400   const svalue *get_rvalue (tree expr, region_model_context *ctxt) const;
 401
 402   const region *deref_rvalue (const svalue *ptr_sval, tree ptr_tree,
 403                                region_model_context *ctxt) const;
 404
 405   const svalue *get_rvalue_for_bits (tree type,
 406                                      const region *reg,
 407                                      const bit_range &bits,
 408                                      region_model_context *ctxt) const;
 409
 410   void set_value (const region *lhs_reg, const svalue *rhs_sval,
 411                   region_model_context *ctxt);
 412   void set_value (tree lhs, tree rhs, region_model_context *ctxt);
 413   void clobber_region (const region *reg);
 414   void purge_region (const region *reg);
 415   void fill_region (const region *reg, const svalue *sval);
 416   void zero_fill_region (const region *reg);
 417   void mark_region_as_unknown (const region *reg, uncertainty_t *uncertainty);
 418
 419   tristate eval_condition (const svalue *lhs,
 420                            enum tree_code op,
 421                            const svalue *rhs) const;
 422   tristate compare_initial_and_pointer (const initial_svalue *init,
 423                                         const region_svalue *ptr) const;
 424   tristate symbolic_greater_than (const binop_svalue *a,
 425                                   const svalue *b) const;
 426   tristate structural_equality (const svalue *a, const svalue *b) const;
 427   tristate eval_condition (tree lhs,
 428                            enum tree_code op,
 429                            tree rhs,
 430                            region_model_context *ctxt) const;
 431   bool add_constraint (tree lhs, enum tree_code op, tree rhs,
 432                        region_model_context *ctxt);
 433   bool add_constraint (tree lhs, enum tree_code op, tree rhs,
 434                        region_model_context *ctxt,
 435                        rejected_constraint **out);
 436
 437   const region *create_region_for_heap_alloc (const svalue *size_in_bytes,
 438                                               region_model_context *ctxt);
 439   const region *create_region_for_alloca (const svalue *size_in_bytes,
 440                                           region_model_context *ctxt);
 441
 442   tree get_representative_tree (const svalue *sval) const;
 443   tree get_representative_tree (const region *reg) const;
 444   path_var
 445   get_representative_path_var (const svalue *sval,
 446                                svalue_set *visited) const;
 447   path_var
 448   get_representative_path_var (const region *reg,
 449                                svalue_set *visited) const;
 450
 451   /* For selftests.  */
 452   constraint_manager *get_constraints ()
 453   {
 454     return m_constraints;
 455   }
 456
 457   store *get_store () { return &m_store; }
 458   const store *get_store () const { return &m_store; }
 459
 460   const dynamic_extents_t &
 461   get_dynamic_extents () const
 462   {
 463     return m_dynamic_extents;
 464   }
 465   const svalue *get_dynamic_extents (const region *reg) const;
 466   void set_dynamic_extents (const region *reg,
 467                             const svalue *size_in_bytes,
 468                             region_model_context *ctxt);
 469   void unset_dynamic_extents (const region *reg);
 470
 471   region_model_manager *get_manager () const { return m_mgr; }
 472   bounded_ranges_manager *get_range_manager () const
 473   {
 474     return m_mgr->get_range_manager ();
 475   }
 476
 477   void unbind_region_and_descendents (const region *reg,
 478                                       enum poison_kind pkind);
 479
 480   bool can_merge_with_p (const region_model &other_model,
 481                          const program_point &point,
 482                          region_model *out_model,
 483                          const extrinsic_state *ext_state = NULL,
 484                          const program_state *state_a = NULL,
 485                          const program_state *state_b = NULL) const;
 486
 487   tree get_fndecl_for_call (const gcall *call,
 488                             region_model_context *ctxt);
 489
 490   void get_regions_for_current_frame (auto_vec<const decl_region *> *out) const;
 491   static void append_regions_cb (const region *base_reg,
 492                                  struct append_regions_cb_data *data);
 493
 494   const svalue *get_store_value (const region *reg,
 495                                  region_model_context *ctxt) const;
 496
 497   bool region_exists_p (const region *reg) const;
 498
 499   void loop_replay_fixup (const region_model *dst_state);
 500
 501   const svalue *get_capacity (const region *reg) const;
 502
 503   const svalue *get_string_size (const svalue *sval) const;
 504   const svalue *get_string_size (const region *reg) const;
 505
 506   bool replay_call_summary (call_summary_replay &r,
 507                             const region_model &summary);
 508
 509   void maybe_complain_about_infoleak (const region *dst_reg,
 510                                       const svalue *copied_sval,
 511                                       const region *src_reg,
 512                                       region_model_context *ctxt);
 513
 514   void set_errno (const call_details &cd);
 515
 516   /* Implemented in sm-fd.cc  */
 517   void mark_as_valid_fd (const svalue *sval, region_model_context *ctxt);
 518
 519   /* Implemented in sm-malloc.cc  */
 520   void on_realloc_with_move (const call_details &cd,
 521                              const svalue *old_ptr_sval,
 522                              const svalue *new_ptr_sval);
 523
 524   /* Implemented in sm-taint.cc.  */
 525   void mark_as_tainted (const svalue *sval,
 526                         region_model_context *ctxt);
 527
 528   bool add_constraint (const svalue *lhs,
 529                        enum tree_code op,
 530                        const svalue *rhs,
 531                        region_model_context *ctxt);
 532
 533   const svalue *check_for_poison (const svalue *sval,
 534                                   tree expr,
 535                                   region_model_context *ctxt) const;
 536
 537   void check_region_for_write (const region *dest_reg,
 538                                region_model_context *ctxt) const;
 539
 540 private:
 541   const region *get_lvalue_1 (path_var pv, region_model_context *ctxt) const;
 542   const svalue *get_rvalue_1 (path_var pv, region_model_context *ctxt) const;
 543
 544   path_var
 545   get_representative_path_var_1 (const svalue *sval,
 546                                  svalue_set *visited) const;
 547   path_var
 548   get_representative_path_var_1 (const region *reg,
 549                                  svalue_set *visited) const;
 550
 551   const known_function *get_known_function (tree fndecl,
 552                                             const call_details &cd) const;
 553   const known_function *get_known_function (enum internal_fn) const;
 554
 555   bool add_constraints_from_binop (const svalue *outer_lhs,
 556                                    enum tree_code outer_op,
 557                                    const svalue *outer_rhs,
 558                                    bool *out,
 559                                    region_model_context *ctxt);
 560
 561   void update_for_call_superedge (const call_superedge &call_edge,
 562                                   region_model_context *ctxt);
 563   void update_for_return_superedge (const return_superedge &return_edge,
 564                                     region_model_context *ctxt);
 565   bool apply_constraints_for_gcond (const cfg_superedge &edge,
 566                                     const gcond *cond_stmt,
 567                                     region_model_context *ctxt,
 568                                     rejected_constraint **out);
 569   bool apply_constraints_for_gswitch (const switch_cfg_superedge &edge,
 570                                       const gswitch *switch_stmt,
 571                                       region_model_context *ctxt,
 572                                       rejected_constraint **out);
 573   bool apply_constraints_for_exception (const gimple *last_stmt,
 574                                         region_model_context *ctxt,
 575                                         rejected_constraint **out);
 576
 577   int poison_any_pointers_to_descendents (const region *reg,
 578                                           enum poison_kind pkind);
 579
 580   void on_top_level_param (tree param, region_model_context *ctxt);
 581
 582   bool called_from_main_p () const;
 583   const svalue *get_initial_value_for_global (const region *reg) const;
 584
 585   const region * get_region_for_poisoned_expr (tree expr) const;
 586
 587   void check_dynamic_size_for_taint (enum memory_space mem_space,
 588                                      const svalue *size_in_bytes,
 589                                      region_model_context *ctxt) const;
 590   void check_dynamic_size_for_floats (const svalue *size_in_bytes,
 591                                       region_model_context *ctxt) const;
 592
 593   void check_region_for_taint (const region *reg,
 594                                enum access_direction dir,
 595                                region_model_context *ctxt) const;
 596
 597   void check_for_writable_region (const region* dest_reg,
 598                                   region_model_context *ctxt) const;
 599   void check_region_access (const region *reg,
 600                             enum access_direction dir,
 601                             region_model_context *ctxt) const;
 602   void check_region_for_read (const region *src_reg,
 603                               region_model_context *ctxt) const;
 604   void check_region_size (const region *lhs_reg, const svalue *rhs_sval,
 605                           region_model_context *ctxt) const;
 606   void check_symbolic_bounds (const region *base_reg,
 607                               const svalue *sym_byte_offset,
 608                               const svalue *num_bytes_sval,
 609                               const svalue *capacity,
 610                               enum access_direction dir,
 611                               region_model_context *ctxt) const;
 612   void check_region_bounds (const region *reg, enum access_direction dir,
 613                             region_model_context *ctxt) const;
 614
 615   void check_call_args (const call_details &cd) const;
 616   void check_external_function_for_access_attr (const gcall *call,
 617                                                 tree callee_fndecl,
 618                                                 region_model_context *ctxt) const;
 619
 620   /* Storing this here to avoid passing it around everywhere.  */
 621   region_model_manager *const m_mgr;
 622
 623   store m_store;
 624
 625   constraint_manager *m_constraints; // TODO: embed, rather than dynalloc?
 626
 627   const frame_region *m_current_frame;
 628
 629   /* Map from base region to size in bytes, for tracking the sizes of
 630      dynamically-allocated regions.
 631      This is part of the region_model rather than the region to allow for
 632      memory regions to be resized (e.g. by realloc).  */
 633   dynamic_extents_t m_dynamic_extents;
 634 };
 635
 636 /* Some region_model activity could lead to warnings (e.g. attempts to use an
 637    uninitialized value).  This abstract base class encapsulates an interface
 638    for the region model to use when emitting such warnings.
 639
 640    Having this as an abstract base class allows us to support the various
 641    operations needed by program_state in the analyzer within region_model,
 642    whilst keeping them somewhat modularized.  */
 643
 644 class region_model_context
 645 {
 646  public:
 647   /* Hook for clients to store pending diagnostics.
 648      Return true if the diagnostic was stored, or false if it was deleted.  */
 649   virtual bool warn (std::unique_ptr<pending_diagnostic> d) = 0;
 650
 651   /* Hook for clients to add a note to the last previously stored
 652      pending diagnostic.  */
 653   virtual void add_note (std::unique_ptr<pending_note> pn) = 0;
 654
 655   /* Hook for clients to be notified when an SVAL that was reachable
 656      in a previous state is no longer live, so that clients can emit warnings
 657      about leaks.  */
 658   virtual void on_svalue_leak (const svalue *sval) = 0;
 659
 660   /* Hook for clients to be notified when the set of explicitly live
 661      svalues changes, so that they can purge state relating to dead
 662      svalues.  */
 663   virtual void on_liveness_change (const svalue_set &live_svalues,
 664                                    const region_model *model) = 0;
 665
 666   virtual logger *get_logger () = 0;
 667
 668   /* Hook for clients to be notified when the condition
 669      "LHS OP RHS" is added to the region model.
 670      This exists so that state machines can detect tests on edges,
 671      and use them to trigger sm-state transitions (e.g. transitions due
 672      to ptrs becoming known to be NULL or non-NULL, rather than just
 673      "unchecked") */
 674   virtual void on_condition (const svalue *lhs,
 675                              enum tree_code op,
 676                              const svalue *rhs) = 0;
 677
 678   /* Hook for clients to be notified when the condition that
 679      SVAL is within RANGES is added to the region model.
 680      Similar to on_condition, but for use when handling switch statements.
 681      RANGES is non-empty.  */
 682   virtual void on_bounded_ranges (const svalue &sval,
 683                                   const bounded_ranges &ranges) = 0;
 684
 685   /* Hook for clients to be notified when a frame is popped from the stack.  */
 686   virtual void on_pop_frame (const frame_region *) = 0;
 687
 688   /* Hooks for clients to be notified when an unknown change happens
 689      to SVAL (in response to a call to an unknown function).  */
 690   virtual void on_unknown_change (const svalue *sval, bool is_mutable) = 0;
 691
 692   /* Hooks for clients to be notified when a phi node is handled,
 693      where RHS is the pertinent argument.  */
 694   virtual void on_phi (const gphi *phi, tree rhs) = 0;
 695
 696   /* Hooks for clients to be notified when the region model doesn't
 697      know how to handle the tree code of T at LOC.  */
 698   virtual void on_unexpected_tree_code (tree t,
 699                                         const dump_location_t &loc) = 0;
 700
 701   /* Hook for clients to be notified when a function_decl escapes.  */
 702   virtual void on_escaped_function (tree fndecl) = 0;
 703
 704   virtual uncertainty_t *get_uncertainty () = 0;
 705
 706   /* Hook for clients to purge state involving SVAL.  */
 707   virtual void purge_state_involving (const svalue *sval) = 0;
 708
 709   /* Hook for clients to split state with a non-standard path.  */
 710   virtual void bifurcate (std::unique_ptr<custom_edge_info> info) = 0;
 711
 712   /* Hook for clients to terminate the standard path.  */
 713   virtual void terminate_path () = 0;
 714
 715   virtual const extrinsic_state *get_ext_state () const = 0;
 716
 717   /* Hook for clients to access the a specific state machine in
 718      any underlying program_state.  */
 719   virtual bool
 720   get_state_map_by_name (const char *name,
 721                          sm_state_map **out_smap,
 722                          const state_machine **out_sm,
 723                          unsigned *out_sm_idx,
 724                          std::unique_ptr<sm_context> *out_sm_context) = 0;
 725
 726   /* Precanned ways for clients to access specific state machines.  */
 727   bool get_fd_map (sm_state_map **out_smap,
 728                    const state_machine **out_sm,
 729                    unsigned *out_sm_idx,
 730                    std::unique_ptr<sm_context> *out_sm_context)
 731   {
 732     return get_state_map_by_name ("file-descriptor", out_smap, out_sm,
 733                                   out_sm_idx, out_sm_context);
 734   }
 735   bool get_malloc_map (sm_state_map **out_smap,
 736                        const state_machine **out_sm,
 737                        unsigned *out_sm_idx)
 738   {
 739     return get_state_map_by_name ("malloc", out_smap, out_sm, out_sm_idx, NULL);
 740   }
 741   bool get_taint_map (sm_state_map **out_smap,
 742                       const state_machine **out_sm,
 743                       unsigned *out_sm_idx)
 744   {
 745     return get_state_map_by_name ("taint", out_smap, out_sm, out_sm_idx, NULL);
 746   }
 747
 748   /* Get the current statement, if any.  */
 749   virtual const gimple *get_stmt () const = 0;
 750 };
 751
 752 /* A "do nothing" subclass of region_model_context.  */
 753
 754 class noop_region_model_context : public region_model_context
 755 {
 756 public:
 757   bool warn (std::unique_ptr<pending_diagnostic>) override { return false; }
 758   void add_note (std::unique_ptr<pending_note>) override;
 759   void on_svalue_leak (const svalue *) override {}
 760   void on_liveness_change (const svalue_set &,
 761                            const region_model *) override {}
 762   logger *get_logger () override { return NULL; }
 763   void on_condition (const svalue *lhs ATTRIBUTE_UNUSED,
 764                      enum tree_code op ATTRIBUTE_UNUSED,
 765                      const svalue *rhs ATTRIBUTE_UNUSED) override
 766   {
 767   }
 768   void on_bounded_ranges (const svalue &,
 769                           const bounded_ranges &) override
 770   {
 771   }
 772   void on_pop_frame (const frame_region *) override {}
 773   void on_unknown_change (const svalue *sval ATTRIBUTE_UNUSED,
 774                           bool is_mutable ATTRIBUTE_UNUSED) override
 775   {
 776   }
 777   void on_phi (const gphi *phi ATTRIBUTE_UNUSED,
 778                tree rhs ATTRIBUTE_UNUSED) override
 779   {
 780   }
 781   void on_unexpected_tree_code (tree, const dump_location_t &) override {}
 782
 783   void on_escaped_function (tree) override {}
 784
 785   uncertainty_t *get_uncertainty () override { return NULL; }
 786
 787   void purge_state_involving (const svalue *sval ATTRIBUTE_UNUSED) override {}
 788
 789   void bifurcate (std::unique_ptr<custom_edge_info> info) override;
 790   void terminate_path () override;
 791
 792   const extrinsic_state *get_ext_state () const override { return NULL; }
 793
 794   bool get_state_map_by_name (const char *,
 795                               sm_state_map **,
 796                               const state_machine **,
 797                               unsigned *,
 798                               std::unique_ptr<sm_context> *) override
 799   {
 800     return false;
 801   }
 802
 803   const gimple *get_stmt () const override { return NULL; }
 804 };
 805
 806 /* A subclass of region_model_context for determining if operations fail
 807    e.g. "can we generate a region for the lvalue of EXPR?".  */
 808
 809 class tentative_region_model_context : public noop_region_model_context
 810 {
 811 public:
 812   tentative_region_model_context () : m_num_unexpected_codes (0) {}
 813
 814   void on_unexpected_tree_code (tree, const dump_location_t &)
 815     final override
 816   {
 817     m_num_unexpected_codes++;
 818   }
 819
 820   bool had_errors_p () const { return m_num_unexpected_codes > 0; }
 821
 822 private:
 823   int m_num_unexpected_codes;
 824 };
 825
 826 /* Subclass of region_model_context that wraps another context, allowing
 827    for extra code to be added to the various hooks.  */
 828
 829 class region_model_context_decorator : public region_model_context
 830 {
 831  public:
 832   bool warn (std::unique_ptr<pending_diagnostic> d) override
 833   {
 834     return m_inner->warn (std::move (d));
 835   }
 836
 837   void add_note (std::unique_ptr<pending_note> pn) override
 838   {
 839     m_inner->add_note (std::move (pn));
 840   }
 841
 842   void on_svalue_leak (const svalue *sval) override
 843   {
 844     m_inner->on_svalue_leak (sval);
 845   }
 846
 847   void on_liveness_change (const svalue_set &live_svalues,
 848                            const region_model *model) override
 849   {
 850     m_inner->on_liveness_change (live_svalues, model);
 851   }
 852
 853   logger *get_logger () override
 854   {
 855     return m_inner->get_logger ();
 856   }
 857
 858   void on_condition (const svalue *lhs,
 859                      enum tree_code op,
 860                      const svalue *rhs) override
 861   {
 862     m_inner->on_condition (lhs, op, rhs);
 863   }
 864
 865   void on_bounded_ranges (const svalue &sval,
 866                           const bounded_ranges &ranges) override
 867   {
 868     m_inner->on_bounded_ranges (sval, ranges);
 869   }
 870
 871   void on_pop_frame (const frame_region *frame_reg) override
 872   {
 873     m_inner->on_pop_frame (frame_reg);
 874   }
 875
 876   void on_unknown_change (const svalue *sval, bool is_mutable) override
 877   {
 878     m_inner->on_unknown_change (sval, is_mutable);
 879   }
 880
 881   void on_phi (const gphi *phi, tree rhs) override
 882   {
 883     m_inner->on_phi (phi, rhs);
 884   }
 885
 886   void on_unexpected_tree_code (tree t,
 887                                 const dump_location_t &loc) override
 888   {
 889     m_inner->on_unexpected_tree_code (t, loc);
 890   }
 891
 892   void on_escaped_function (tree fndecl) override
 893   {
 894     m_inner->on_escaped_function (fndecl);
 895   }
 896
 897   uncertainty_t *get_uncertainty () override
 898   {
 899     return m_inner->get_uncertainty ();
 900   }
 901
 902   void purge_state_involving (const svalue *sval) override
 903   {
 904     m_inner->purge_state_involving (sval);
 905   }
 906
 907   void bifurcate (std::unique_ptr<custom_edge_info> info) override
 908   {
 909     m_inner->bifurcate (std::move (info));
 910   }
 911
 912   void terminate_path () override
 913   {
 914     m_inner->terminate_path ();
 915   }
 916
 917   const extrinsic_state *get_ext_state () const override
 918   {
 919     return m_inner->get_ext_state ();
 920   }
 921
 922   bool get_state_map_by_name (const char *name,
 923                               sm_state_map **out_smap,
 924                               const state_machine **out_sm,
 925                               unsigned *out_sm_idx,
 926                               std::unique_ptr<sm_context> *out_sm_context)
 927     override
 928   {
 929     return m_inner->get_state_map_by_name (name, out_smap, out_sm, out_sm_idx,
 930                                            out_sm_context);
 931   }
 932
 933   const gimple *get_stmt () const override
 934   {
 935     return m_inner->get_stmt ();
 936   }
 937
 938 protected:
 939   region_model_context_decorator (region_model_context *inner)
 940   : m_inner (inner)
 941   {
 942     gcc_assert (m_inner);
 943   }
 944
 945   region_model_context *m_inner;
 946 };
 947
 948 /* Subclass of region_model_context_decorator that adds a note
 949    when saving diagnostics.  */
 950
 951 class note_adding_context : public region_model_context_decorator
 952 {
 953 public:
 954   bool warn (std::unique_ptr<pending_diagnostic> d) override
 955   {
 956     if (m_inner->warn (std::move (d)))
 957       {
 958         add_note (make_note ());
 959         return true;
 960       }
 961     else
 962       return false;
 963   }
 964
 965   /* Hook to make the new note.  */
 966   virtual std::unique_ptr<pending_note> make_note () = 0;
 967
 968 protected:
 969   note_adding_context (region_model_context *inner)
 970   : region_model_context_decorator (inner)
 971   {
 972   }
 973 };
 974
 975 /* A bundle of data for use when attempting to merge two region_model
 976    instances to make a third.  */
 977
 978 struct model_merger
 979 {
 980   model_merger (const region_model *model_a,
 981                 const region_model *model_b,
 982                 const program_point &point,
 983                 region_model *merged_model,
 984                 const extrinsic_state *ext_state,
 985                 const program_state *state_a,
 986                 const program_state *state_b)
 987   : m_model_a (model_a), m_model_b (model_b),
 988     m_point (point),
 989     m_merged_model (merged_model),
 990     m_ext_state (ext_state),
 991     m_state_a (state_a), m_state_b (state_b)
 992   {
 993   }
 994
 995   void dump_to_pp (pretty_printer *pp, bool simple) const;
 996   void dump (FILE *fp, bool simple) const;
 997   void dump (bool simple) const;
 998
 999   region_model_manager *get_manager () const
1000   {
1001     return m_model_a->get_manager ();
1002   }
1003
1004   bool mergeable_svalue_p (const svalue *) const;
1005   const function_point &get_function_point () const
1006   {
1007     return m_point.get_function_point ();
1008   }
1009
1010   const region_model *m_model_a;
1011   const region_model *m_model_b;
1012   const program_point &m_point;
1013   region_model *m_merged_model;
1014
1015   const extrinsic_state *m_ext_state;
1016   const program_state *m_state_a;
1017   const program_state *m_state_b;
1018 };
1019
1020 /* A record that can (optionally) be written out when
1021    region_model::add_constraint fails.  */
1022
1023 class rejected_constraint
1024 {
1025 public:
1026   virtual ~rejected_constraint () {}
1027   virtual void dump_to_pp (pretty_printer *pp) const = 0;
1028
1029   const region_model &get_model () const { return m_model; }
1030
1031 protected:
1032   rejected_constraint (const region_model &model)
1033   : m_model (model)
1034   {}
1035
1036   region_model m_model;
1037 };
1038
1039 class rejected_op_constraint : public rejected_constraint
1040 {
1041 public:
1042   rejected_op_constraint (const region_model &model,
1043                           tree lhs, enum tree_code op, tree rhs)
1044   : rejected_constraint (model),
1045     m_lhs (lhs), m_op (op), m_rhs (rhs)
1046   {}
1047
1048   void dump_to_pp (pretty_printer *pp) const final override;
1049
1050   tree m_lhs;
1051   enum tree_code m_op;
1052   tree m_rhs;
1053 };
1054
1055 class rejected_ranges_constraint : public rejected_constraint
1056 {
1057 public:
1058   rejected_ranges_constraint (const region_model &model,
1059                               tree expr, const bounded_ranges *ranges)
1060   : rejected_constraint (model),
1061     m_expr (expr), m_ranges (ranges)
1062   {}
1063
1064   void dump_to_pp (pretty_printer *pp) const final override;
1065
1066 private:
1067   tree m_expr;
1068   const bounded_ranges *m_ranges;
1069 };
1070
1071 /* A bundle of state.  */
1072
1073 class engine
1074 {
1075 public:
1076   engine (const supergraph *sg = NULL, logger *logger = NULL);
1077   const supergraph *get_supergraph () { return m_sg; }
1078   region_model_manager *get_model_manager () { return &m_mgr; }
1079   known_function_manager *get_known_function_manager ()
1080   {
1081     return m_mgr.get_known_function_manager ();
1082   }
1083
1084   void log_stats (logger *logger) const;
1085
1086 private:
1087   const supergraph *m_sg;
1088   region_model_manager m_mgr;
1089 };
1090
1091 } // namespace ana
1092
1093 extern void debug (const region_model &rmodel);
1094
1095 namespace ana {
1096
1097 #if CHECKING_P
1098
1099 namespace selftest {
1100
1101 using namespace ::selftest;
1102
1103 /* An implementation of region_model_context for use in selftests, which
1104    stores any pending_diagnostic instances passed to it.  */
1105
1106 class test_region_model_context : public noop_region_model_context
1107 {
1108 public:
1109   bool warn (std::unique_ptr<pending_diagnostic> d) final override
1110   {
1111     m_diagnostics.safe_push (d.release ());
1112     return true;
1113   }
1114
1115   unsigned get_num_diagnostics () const { return m_diagnostics.length (); }
1116
1117   void on_unexpected_tree_code (tree t, const dump_location_t &)
1118     final override
1119   {
1120     internal_error ("unhandled tree code: %qs",
1121                     get_tree_code_name (TREE_CODE (t)));
1122   }
1123
1124 private:
1125   /* Implicitly delete any diagnostics in the dtor.  */
1126   auto_delete_vec<pending_diagnostic> m_diagnostics;
1127 };
1128
1129 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1130    Verify that MODEL remains satisfiable.  */
1131
1132 #define ADD_SAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
1133   SELFTEST_BEGIN_STMT                                   \
1134     bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL);     \
1135     ASSERT_TRUE (sat);                                  \
1136   SELFTEST_END_STMT
1137
1138 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1139    Verify that the result is not satisfiable.  */
1140
1141 #define ADD_UNSAT_CONSTRAINT(MODEL, LHS, OP, RHS)       \
1142   SELFTEST_BEGIN_STMT                                   \
1143     bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL);     \
1144     ASSERT_FALSE (sat);                         \
1145   SELFTEST_END_STMT
1146
1147 /* Implementation detail of the ASSERT_CONDITION_* macros.  */
1148
1149 void assert_condition (const location &loc,
1150                        region_model &model,
1151                        const svalue *lhs, tree_code op, const svalue *rhs,
1152                        tristate expected);
1153
1154 void assert_condition (const location &loc,
1155                        region_model &model,
1156                        tree lhs, tree_code op, tree rhs,
1157                        tristate expected);
1158
1159 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1160    as "true".  */
1161
1162 #define ASSERT_CONDITION_TRUE(REGION_MODEL, LHS, OP, RHS) \
1163   SELFTEST_BEGIN_STMT                                                   \
1164   assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,      \
1165                     tristate (tristate::TS_TRUE));              \
1166   SELFTEST_END_STMT
1167
1168 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1169    as "false".  */
1170
1171 #define ASSERT_CONDITION_FALSE(REGION_MODEL, LHS, OP, RHS) \
1172   SELFTEST_BEGIN_STMT                                                   \
1173   assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,      \
1174                     tristate (tristate::TS_FALSE));             \
1175   SELFTEST_END_STMT
1176
1177 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1178    as "unknown".  */
1179
1180 #define ASSERT_CONDITION_UNKNOWN(REGION_MODEL, LHS, OP, RHS) \
1181   SELFTEST_BEGIN_STMT                                                   \
1182   assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,      \
1183                     tristate (tristate::TS_UNKNOWN));           \
1184   SELFTEST_END_STMT
1185
1186 } /* end of namespace selftest.  */
1187
1188 #endif /* #if CHECKING_P */
1189
1190 } // namespace ana
1191
1192 #endif /* GCC_ANALYZER_REGION_MODEL_H */