gcc/analyzer/region-model.h

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