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 mark_region_as_unknown (const region *reg, uncertainty_t *uncertainty);
 371
 372   tristate eval_condition (const svalue *lhs,
 373                            enum tree_code op,
 374                            const svalue *rhs) const;
 375   tristate compare_initial_and_pointer (const initial_svalue *init,
 376                                         const region_svalue *ptr) const;
 377   tristate symbolic_greater_than (const binop_svalue *a,
 378                                   const svalue *b) const;
 379   tristate structural_equality (const svalue *a, const svalue *b) const;
 380   tristate eval_condition (tree lhs,
 381                            enum tree_code op,
 382                            tree rhs,
 383                            region_model_context *ctxt) const;
 384   bool add_constraint (tree lhs, enum tree_code op, tree rhs,
 385                        region_model_context *ctxt);
 386   bool add_constraint (tree lhs, enum tree_code op, tree rhs,
 387                        region_model_context *ctxt,
 388                        rejected_constraint **out);
 389
 390         const region *
 391         get_or_create_region_for_heap_alloc (const svalue *size_in_bytes,
 392                                 region_model_context *ctxt,
 393                                 bool update_state_machine = false,
 394                                 const call_details *cd = nullptr);
 395
 396   const region *create_region_for_alloca (const svalue *size_in_bytes,
 397                                           region_model_context *ctxt);
 398   void get_referenced_base_regions (auto_bitmap &out_ids) const;
 399
 400   tree get_representative_tree (const svalue *sval) const;
 401   tree get_representative_tree (const region *reg) const;
 402   path_var
 403   get_representative_path_var (const svalue *sval,
 404                                svalue_set *visited) const;
 405   path_var
 406   get_representative_path_var (const region *reg,
 407                                svalue_set *visited) const;
 408
 409   /* For selftests.  */
 410   constraint_manager *get_constraints ()
 411   {
 412     return m_constraints;
 413   }
 414
 415   store *get_store () { return &m_store; }
 416   const store *get_store () const { return &m_store; }
 417
 418   const dynamic_extents_t &
 419   get_dynamic_extents () const
 420   {
 421     return m_dynamic_extents;
 422   }
 423   const svalue *get_dynamic_extents (const region *reg) const;
 424   void set_dynamic_extents (const region *reg,
 425                             const svalue *size_in_bytes,
 426                             region_model_context *ctxt);
 427   void unset_dynamic_extents (const region *reg);
 428
 429   region_model_manager *get_manager () const { return m_mgr; }
 430   bounded_ranges_manager *get_range_manager () const
 431   {
 432     return m_mgr->get_range_manager ();
 433   }
 434
 435   void unbind_region_and_descendents (const region *reg,
 436                                       enum poison_kind pkind);
 437
 438   bool can_merge_with_p (const region_model &other_model,
 439                          const program_point &point,
 440                          region_model *out_model,
 441                          const extrinsic_state *ext_state = NULL,
 442                          const program_state *state_a = NULL,
 443                          const program_state *state_b = NULL) const;
 444
 445   tree get_fndecl_for_call (const gcall *call,
 446                             region_model_context *ctxt);
 447
 448   void get_regions_for_current_frame (auto_vec<const decl_region *> *out) const;
 449   static void append_regions_cb (const region *base_reg,
 450                                  struct append_regions_cb_data *data);
 451
 452   const svalue *get_store_value (const region *reg,
 453                                  region_model_context *ctxt) const;
 454   const svalue *get_store_bytes (const region *base_reg,
 455                                  const byte_range &bytes,
 456                                  region_model_context *ctxt) const;
 457   const svalue *scan_for_null_terminator (const region *reg,
 458                                           tree expr,
 459                                           const svalue **out_sval,
 460                                           region_model_context *ctxt) const;
 461
 462   bool region_exists_p (const region *reg) const;
 463
 464   void loop_replay_fixup (const region_model *dst_state);
 465
 466   const svalue *get_capacity (const region *reg) const;
 467
 468   const svalue *get_string_size (const svalue *sval) const;
 469   const svalue *get_string_size (const region *reg) const;
 470
 471   bool replay_call_summary (call_summary_replay &r,
 472                             const region_model &summary);
 473
 474   void maybe_complain_about_infoleak (const region *dst_reg,
 475                                       const svalue *copied_sval,
 476                                       const region *src_reg,
 477                                       region_model_context *ctxt);
 478
 479   void set_errno (const call_details &cd);
 480
 481   /* Implemented in sm-fd.cc  */
 482   void mark_as_valid_fd (const svalue *sval, region_model_context *ctxt);
 483
 484   /* Implemented in sm-malloc.cc  */
 485   void on_realloc_with_move (const call_details &cd,
 486                              const svalue *old_ptr_sval,
 487                              const svalue *new_ptr_sval);
 488
 489   /* Implemented in sm-malloc.cc.  */
 490   void
 491   transition_ptr_sval_non_null (region_model_context *ctxt,
 492       const svalue *new_ptr_sval);
 493
 494   /* Implemented in sm-taint.cc.  */
 495   void mark_as_tainted (const svalue *sval,
 496                         region_model_context *ctxt);
 497
 498   bool add_constraint (const svalue *lhs,
 499                        enum tree_code op,
 500                        const svalue *rhs,
 501                        region_model_context *ctxt);
 502
 503   const svalue *check_for_poison (const svalue *sval,
 504                                   tree expr,
 505                                   const region *src_region,
 506                                   region_model_context *ctxt) const;
 507
 508   void check_region_for_write (const region *dest_reg,
 509                                const svalue *sval_hint,
 510                                region_model_context *ctxt) const;
 511
 512   const svalue *
 513   check_for_null_terminated_string_arg (const call_details &cd,
 514                                         unsigned idx,
 515                                         const svalue **out_sval = nullptr);
 516
 517 private:
 518   const region *get_lvalue_1 (path_var pv, region_model_context *ctxt) const;
 519   const svalue *get_rvalue_1 (path_var pv, region_model_context *ctxt) const;
 520
 521   path_var
 522   get_representative_path_var_1 (const svalue *sval,
 523                                  svalue_set *visited) const;
 524   path_var
 525   get_representative_path_var_1 (const region *reg,
 526                                  svalue_set *visited) const;
 527
 528   const known_function *get_known_function (tree fndecl,
 529                                             const call_details &cd) const;
 530   const known_function *get_known_function (enum internal_fn) const;
 531
 532   bool add_constraints_from_binop (const svalue *outer_lhs,
 533                                    enum tree_code outer_op,
 534                                    const svalue *outer_rhs,
 535                                    bool *out,
 536                                    region_model_context *ctxt);
 537
 538   void update_for_call_superedge (const call_superedge &call_edge,
 539                                   region_model_context *ctxt);
 540   void update_for_return_superedge (const return_superedge &return_edge,
 541                                     region_model_context *ctxt);
 542   bool apply_constraints_for_gcond (const cfg_superedge &edge,
 543                                     const gcond *cond_stmt,
 544                                     region_model_context *ctxt,
 545                                     rejected_constraint **out);
 546   bool apply_constraints_for_gswitch (const switch_cfg_superedge &edge,
 547                                       const gswitch *switch_stmt,
 548                                       region_model_context *ctxt,
 549                                       rejected_constraint **out);
 550   bool apply_constraints_for_exception (const gimple *last_stmt,
 551                                         region_model_context *ctxt,
 552                                         rejected_constraint **out);
 553
 554   int poison_any_pointers_to_descendents (const region *reg,
 555                                           enum poison_kind pkind);
 556
 557   void on_top_level_param (tree param,
 558                            bool nonnull,
 559                            region_model_context *ctxt);
 560
 561   bool called_from_main_p () const;
 562   const svalue *get_initial_value_for_global (const region *reg) const;
 563
 564   const region * get_region_for_poisoned_expr (tree expr) const;
 565
 566   void check_dynamic_size_for_taint (enum memory_space mem_space,
 567                                      const svalue *size_in_bytes,
 568                                      region_model_context *ctxt) const;
 569   void check_dynamic_size_for_floats (const svalue *size_in_bytes,
 570                                       region_model_context *ctxt) const;
 571
 572   void check_region_for_taint (const region *reg,
 573                                enum access_direction dir,
 574                                region_model_context *ctxt) const;
 575
 576   void check_for_writable_region (const region* dest_reg,
 577                                   region_model_context *ctxt) const;
 578   bool check_region_access (const region *reg,
 579                             enum access_direction dir,
 580                             const svalue *sval_hint,
 581                             region_model_context *ctxt) const;
 582   bool check_region_for_read (const region *src_reg,
 583                               region_model_context *ctxt) const;
 584   void check_region_size (const region *lhs_reg, const svalue *rhs_sval,
 585                           region_model_context *ctxt) const;
 586
 587   /* Implemented in bounds-checking.cc  */
 588   bool check_symbolic_bounds (const region *base_reg,
 589                               const svalue *sym_byte_offset,
 590                               const svalue *num_bytes_sval,
 591                               const svalue *capacity,
 592                               enum access_direction dir,
 593                               const svalue *sval_hint,
 594                               region_model_context *ctxt) const;
 595   bool check_region_bounds (const region *reg, enum access_direction dir,
 596                             const svalue *sval_hint,
 597                             region_model_context *ctxt) const;
 598
 599   void check_call_args (const call_details &cd) const;
 600   void check_external_function_for_access_attr (const gcall *call,
 601                                                 tree callee_fndecl,
 602                                                 region_model_context *ctxt) const;
 603
 604   /* Storing this here to avoid passing it around everywhere.  */
 605   region_model_manager *const m_mgr;
 606
 607   store m_store;
 608
 609   constraint_manager *m_constraints; // TODO: embed, rather than dynalloc?
 610
 611   const frame_region *m_current_frame;
 612
 613   /* Map from base region to size in bytes, for tracking the sizes of
 614      dynamically-allocated regions.
 615      This is part of the region_model rather than the region to allow for
 616      memory regions to be resized (e.g. by realloc).  */
 617   dynamic_extents_t m_dynamic_extents;
 618 };
 619
 620 /* Some region_model activity could lead to warnings (e.g. attempts to use an
 621    uninitialized value).  This abstract base class encapsulates an interface
 622    for the region model to use when emitting such warnings.
 623
 624    Having this as an abstract base class allows us to support the various
 625    operations needed by program_state in the analyzer within region_model,
 626    whilst keeping them somewhat modularized.  */
 627
 628 class region_model_context
 629 {
 630  public:
 631   /* Hook for clients to store pending diagnostics.
 632      Return true if the diagnostic was stored, or false if it was deleted.  */
 633   virtual bool warn (std::unique_ptr<pending_diagnostic> d) = 0;
 634
 635   /* Hook for clients to add a note to the last previously stored
 636      pending diagnostic.  */
 637   virtual void add_note (std::unique_ptr<pending_note> pn) = 0;
 638
 639   /* Hook for clients to add an event to the last previously stored
 640      pending diagnostic.  */
 641   virtual void add_event (std::unique_ptr<checker_event> event) = 0;
 642
 643   /* Hook for clients to be notified when an SVAL that was reachable
 644      in a previous state is no longer live, so that clients can emit warnings
 645      about leaks.  */
 646   virtual void on_svalue_leak (const svalue *sval) = 0;
 647
 648   /* Hook for clients to be notified when the set of explicitly live
 649      svalues changes, so that they can purge state relating to dead
 650      svalues.  */
 651   virtual void on_liveness_change (const svalue_set &live_svalues,
 652                                    const region_model *model) = 0;
 653
 654   virtual logger *get_logger () = 0;
 655
 656   /* Hook for clients to be notified when the condition
 657      "LHS OP RHS" is added to the region model.
 658      This exists so that state machines can detect tests on edges,
 659      and use them to trigger sm-state transitions (e.g. transitions due
 660      to ptrs becoming known to be NULL or non-NULL, rather than just
 661      "unchecked") */
 662   virtual void on_condition (const svalue *lhs,
 663                              enum tree_code op,
 664                              const svalue *rhs) = 0;
 665
 666   /* Hook for clients to be notified when the condition that
 667      SVAL is within RANGES is added to the region model.
 668      Similar to on_condition, but for use when handling switch statements.
 669      RANGES is non-empty.  */
 670   virtual void on_bounded_ranges (const svalue &sval,
 671                                   const bounded_ranges &ranges) = 0;
 672
 673   /* Hook for clients to be notified when a frame is popped from the stack.  */
 674   virtual void on_pop_frame (const frame_region *) = 0;
 675
 676   /* Hooks for clients to be notified when an unknown change happens
 677      to SVAL (in response to a call to an unknown function).  */
 678   virtual void on_unknown_change (const svalue *sval, bool is_mutable) = 0;
 679
 680   /* Hooks for clients to be notified when a phi node is handled,
 681      where RHS is the pertinent argument.  */
 682   virtual void on_phi (const gphi *phi, tree rhs) = 0;
 683
 684   /* Hooks for clients to be notified when the region model doesn't
 685      know how to handle the tree code of T at LOC.  */
 686   virtual void on_unexpected_tree_code (tree t,
 687                                         const dump_location_t &loc) = 0;
 688
 689   /* Hook for clients to be notified when a function_decl escapes.  */
 690   virtual void on_escaped_function (tree fndecl) = 0;
 691
 692   virtual uncertainty_t *get_uncertainty () = 0;
 693
 694   /* Hook for clients to purge state involving SVAL.  */
 695   virtual void purge_state_involving (const svalue *sval) = 0;
 696
 697   /* Hook for clients to split state with a non-standard path.  */
 698   virtual void bifurcate (std::unique_ptr<custom_edge_info> info) = 0;
 699
 700   /* Hook for clients to terminate the standard path.  */
 701   virtual void terminate_path () = 0;
 702
 703   virtual const extrinsic_state *get_ext_state () const = 0;
 704
 705   /* Hook for clients to access the a specific state machine in
 706      any underlying program_state.  */
 707   virtual bool
 708   get_state_map_by_name (const char *name,
 709                          sm_state_map **out_smap,
 710                          const state_machine **out_sm,
 711                          unsigned *out_sm_idx,
 712                          std::unique_ptr<sm_context> *out_sm_context) = 0;
 713
 714   /* Precanned ways for clients to access specific state machines.  */
 715   bool get_fd_map (sm_state_map **out_smap,
 716                    const state_machine **out_sm,
 717                    unsigned *out_sm_idx,
 718                    std::unique_ptr<sm_context> *out_sm_context)
 719   {
 720     return get_state_map_by_name ("file-descriptor", out_smap, out_sm,
 721                                   out_sm_idx, out_sm_context);
 722   }
 723   bool get_malloc_map (sm_state_map **out_smap,
 724                        const state_machine **out_sm,
 725                        unsigned *out_sm_idx)
 726   {
 727     return get_state_map_by_name ("malloc", out_smap, out_sm, out_sm_idx, NULL);
 728   }
 729   bool get_taint_map (sm_state_map **out_smap,
 730                       const state_machine **out_sm,
 731                       unsigned *out_sm_idx)
 732   {
 733     return get_state_map_by_name ("taint", out_smap, out_sm, out_sm_idx, NULL);
 734   }
 735
 736   bool possibly_tainted_p (const svalue *sval);
 737
 738   /* Get the current statement, if any.  */
 739   virtual const gimple *get_stmt () const = 0;
 740 };
 741
 742 /* A "do nothing" subclass of region_model_context.  */
 743
 744 class noop_region_model_context : public region_model_context
 745 {
 746 public:
 747   bool warn (std::unique_ptr<pending_diagnostic>) override { return false; }
 748   void add_note (std::unique_ptr<pending_note>) override;
 749   void add_event (std::unique_ptr<checker_event>) override;
 750   void on_svalue_leak (const svalue *) override {}
 751   void on_liveness_change (const svalue_set &,
 752                            const region_model *) override {}
 753   logger *get_logger () override { return NULL; }
 754   void on_condition (const svalue *lhs ATTRIBUTE_UNUSED,
 755                      enum tree_code op ATTRIBUTE_UNUSED,
 756                      const svalue *rhs ATTRIBUTE_UNUSED) override
 757   {
 758   }
 759   void on_bounded_ranges (const svalue &,
 760                           const bounded_ranges &) override
 761   {
 762   }
 763   void on_pop_frame (const frame_region *) override {}
 764   void on_unknown_change (const svalue *sval ATTRIBUTE_UNUSED,
 765                           bool is_mutable ATTRIBUTE_UNUSED) override
 766   {
 767   }
 768   void on_phi (const gphi *phi ATTRIBUTE_UNUSED,
 769                tree rhs ATTRIBUTE_UNUSED) override
 770   {
 771   }
 772   void on_unexpected_tree_code (tree, const dump_location_t &) override {}
 773
 774   void on_escaped_function (tree) override {}
 775
 776   uncertainty_t *get_uncertainty () override { return NULL; }
 777
 778   void purge_state_involving (const svalue *sval ATTRIBUTE_UNUSED) override {}
 779
 780   void bifurcate (std::unique_ptr<custom_edge_info> info) override;
 781   void terminate_path () override;
 782
 783   const extrinsic_state *get_ext_state () const override { return NULL; }
 784
 785   bool get_state_map_by_name (const char *,
 786                               sm_state_map **,
 787                               const state_machine **,
 788                               unsigned *,
 789                               std::unique_ptr<sm_context> *) override
 790   {
 791     return false;
 792   }
 793
 794   const gimple *get_stmt () const override { return NULL; }
 795 };
 796
 797 /* A subclass of region_model_context for determining if operations fail
 798    e.g. "can we generate a region for the lvalue of EXPR?".  */
 799
 800 class tentative_region_model_context : public noop_region_model_context
 801 {
 802 public:
 803   tentative_region_model_context () : m_num_unexpected_codes (0) {}
 804
 805   void on_unexpected_tree_code (tree, const dump_location_t &)
 806     final override
 807   {
 808     m_num_unexpected_codes++;
 809   }
 810
 811   bool had_errors_p () const { return m_num_unexpected_codes > 0; }
 812
 813 private:
 814   int m_num_unexpected_codes;
 815 };
 816
 817 /* Subclass of region_model_context that wraps another context, allowing
 818    for extra code to be added to the various hooks.  */
 819
 820 class region_model_context_decorator : public region_model_context
 821 {
 822  public:
 823   bool warn (std::unique_ptr<pending_diagnostic> d) override
 824   {
 825     if (m_inner)
 826       return m_inner->warn (std::move (d));
 827     else
 828       return false;
 829   }
 830
 831   void add_note (std::unique_ptr<pending_note> pn) override
 832   {
 833     if (m_inner)
 834       m_inner->add_note (std::move (pn));
 835   }
 836   void add_event (std::unique_ptr<checker_event> event) override;
 837
 838   void on_svalue_leak (const svalue *sval) override
 839   {
 840     if (m_inner)
 841       m_inner->on_svalue_leak (sval);
 842   }
 843
 844   void on_liveness_change (const svalue_set &live_svalues,
 845                            const region_model *model) override
 846   {
 847     if (m_inner)
 848       m_inner->on_liveness_change (live_svalues, model);
 849   }
 850
 851   logger *get_logger () override
 852   {
 853     if (m_inner)
 854       return m_inner->get_logger ();
 855     else
 856       return nullptr;
 857   }
 858
 859   void on_condition (const svalue *lhs,
 860                      enum tree_code op,
 861                      const svalue *rhs) override
 862   {
 863     if (m_inner)
 864       m_inner->on_condition (lhs, op, rhs);
 865   }
 866
 867   void on_bounded_ranges (const svalue &sval,
 868                           const bounded_ranges &ranges) override
 869   {
 870     if (m_inner)
 871       m_inner->on_bounded_ranges (sval, ranges);
 872   }
 873
 874   void on_pop_frame (const frame_region *frame_reg) override
 875   {
 876     if (m_inner)
 877       m_inner->on_pop_frame (frame_reg);
 878   }
 879
 880   void on_unknown_change (const svalue *sval, bool is_mutable) override
 881   {
 882     if (m_inner)
 883       m_inner->on_unknown_change (sval, is_mutable);
 884   }
 885
 886   void on_phi (const gphi *phi, tree rhs) override
 887   {
 888     if (m_inner)
 889       m_inner->on_phi (phi, rhs);
 890   }
 891
 892   void on_unexpected_tree_code (tree t,
 893                                 const dump_location_t &loc) override
 894   {
 895     if (m_inner)
 896       m_inner->on_unexpected_tree_code (t, loc);
 897   }
 898
 899   void on_escaped_function (tree fndecl) override
 900   {
 901     if (m_inner)
 902       m_inner->on_escaped_function (fndecl);
 903   }
 904
 905   uncertainty_t *get_uncertainty () override
 906   {
 907     if (m_inner)
 908       return m_inner->get_uncertainty ();
 909     else
 910       return nullptr;
 911   }
 912
 913   void purge_state_involving (const svalue *sval) override
 914   {
 915     if (m_inner)
 916       m_inner->purge_state_involving (sval);
 917   }
 918
 919   void bifurcate (std::unique_ptr<custom_edge_info> info) override
 920   {
 921     if (m_inner)
 922       m_inner->bifurcate (std::move (info));
 923   }
 924
 925   void terminate_path () override
 926   {
 927     if (m_inner)
 928       m_inner->terminate_path ();
 929   }
 930
 931   const extrinsic_state *get_ext_state () const override
 932   {
 933     if (m_inner)
 934       return m_inner->get_ext_state ();
 935     else
 936       return nullptr;
 937   }
 938
 939   bool get_state_map_by_name (const char *name,
 940                               sm_state_map **out_smap,
 941                               const state_machine **out_sm,
 942                               unsigned *out_sm_idx,
 943                               std::unique_ptr<sm_context> *out_sm_context)
 944     override
 945   {
 946     if (m_inner)
 947       return m_inner->get_state_map_by_name (name, out_smap, out_sm, out_sm_idx,
 948                                              out_sm_context);
 949     else
 950       return false;
 951   }
 952
 953   const gimple *get_stmt () const override
 954   {
 955     if (m_inner)
 956       return m_inner->get_stmt ();
 957     else
 958       return nullptr;
 959   }
 960
 961 protected:
 962   region_model_context_decorator (region_model_context *inner)
 963   : m_inner (inner)
 964   {
 965   }
 966
 967   region_model_context *m_inner;
 968 };
 969
 970 /* Subclass of region_model_context_decorator with a hook for adding
 971    notes/events when saving diagnostics.  */
 972
 973 class annotating_context : public region_model_context_decorator
 974 {
 975 public:
 976   bool warn (std::unique_ptr<pending_diagnostic> d) override
 977   {
 978     if (m_inner)
 979       if (m_inner->warn (std::move (d)))
 980         {
 981           add_annotations ();
 982           return true;
 983         }
 984     return false;
 985   }
 986
 987   /* Hook to add new event(s)/note(s)  */
 988   virtual void add_annotations () = 0;
 989
 990 protected:
 991   annotating_context (region_model_context *inner)
 992   : region_model_context_decorator (inner)
 993   {
 994   }
 995 };
 996
 997 /* A bundle of data for use when attempting to merge two region_model
 998    instances to make a third.  */
 999
1000 struct model_merger
1001 {
1002   model_merger (const region_model *model_a,
1003                 const region_model *model_b,
1004                 const program_point &point,
1005                 region_model *merged_model,
1006                 const extrinsic_state *ext_state,
1007                 const program_state *state_a,
1008                 const program_state *state_b)
1009   : m_model_a (model_a), m_model_b (model_b),
1010     m_point (point),
1011     m_merged_model (merged_model),
1012     m_ext_state (ext_state),
1013     m_state_a (state_a), m_state_b (state_b)
1014   {
1015   }
1016
1017   void dump_to_pp (pretty_printer *pp, bool simple) const;
1018   void dump (FILE *fp, bool simple) const;
1019   void dump (bool simple) const;
1020
1021   region_model_manager *get_manager () const
1022   {
1023     return m_model_a->get_manager ();
1024   }
1025
1026   bool mergeable_svalue_p (const svalue *) const;
1027   const function_point &get_function_point () const
1028   {
1029     return m_point.get_function_point ();
1030   }
1031
1032   const region_model *m_model_a;
1033   const region_model *m_model_b;
1034   const program_point &m_point;
1035   region_model *m_merged_model;
1036
1037   const extrinsic_state *m_ext_state;
1038   const program_state *m_state_a;
1039   const program_state *m_state_b;
1040 };
1041
1042 /* A record that can (optionally) be written out when
1043    region_model::add_constraint fails.  */
1044
1045 class rejected_constraint
1046 {
1047 public:
1048   virtual ~rejected_constraint () {}
1049   virtual void dump_to_pp (pretty_printer *pp) const = 0;
1050
1051   const region_model &get_model () const { return m_model; }
1052
1053 protected:
1054   rejected_constraint (const region_model &model)
1055   : m_model (model)
1056   {}
1057
1058   region_model m_model;
1059 };
1060
1061 class rejected_op_constraint : public rejected_constraint
1062 {
1063 public:
1064   rejected_op_constraint (const region_model &model,
1065                           tree lhs, enum tree_code op, tree rhs)
1066   : rejected_constraint (model),
1067     m_lhs (lhs), m_op (op), m_rhs (rhs)
1068   {}
1069
1070   void dump_to_pp (pretty_printer *pp) const final override;
1071
1072   tree m_lhs;
1073   enum tree_code m_op;
1074   tree m_rhs;
1075 };
1076
1077 class rejected_default_case : public rejected_constraint
1078 {
1079 public:
1080   rejected_default_case (const region_model &model)
1081   : rejected_constraint (model)
1082   {}
1083
1084   void dump_to_pp (pretty_printer *pp) const final override;
1085 };
1086
1087 class rejected_ranges_constraint : public rejected_constraint
1088 {
1089 public:
1090   rejected_ranges_constraint (const region_model &model,
1091                               tree expr, const bounded_ranges *ranges)
1092   : rejected_constraint (model),
1093     m_expr (expr), m_ranges (ranges)
1094   {}
1095
1096   void dump_to_pp (pretty_printer *pp) const final override;
1097
1098 private:
1099   tree m_expr;
1100   const bounded_ranges *m_ranges;
1101 };
1102
1103 /* A bundle of state.  */
1104
1105 class engine
1106 {
1107 public:
1108   engine (const supergraph *sg = NULL, logger *logger = NULL);
1109   const supergraph *get_supergraph () { return m_sg; }
1110   region_model_manager *get_model_manager () { return &m_mgr; }
1111   known_function_manager *get_known_function_manager ()
1112   {
1113     return m_mgr.get_known_function_manager ();
1114   }
1115
1116   void log_stats (logger *logger) const;
1117
1118 private:
1119   const supergraph *m_sg;
1120   region_model_manager m_mgr;
1121 };
1122
1123 } // namespace ana
1124
1125 extern void debug (const region_model &rmodel);
1126
1127 namespace ana {
1128
1129 #if CHECKING_P
1130
1131 namespace selftest {
1132
1133 using namespace ::selftest;
1134
1135 /* An implementation of region_model_context for use in selftests, which
1136    stores any pending_diagnostic instances passed to it.  */
1137
1138 class test_region_model_context : public noop_region_model_context
1139 {
1140 public:
1141   bool warn (std::unique_ptr<pending_diagnostic> d) final override
1142   {
1143     m_diagnostics.safe_push (d.release ());
1144     return true;
1145   }
1146
1147   unsigned get_num_diagnostics () const { return m_diagnostics.length (); }
1148
1149   void on_unexpected_tree_code (tree t, const dump_location_t &)
1150     final override
1151   {
1152     internal_error ("unhandled tree code: %qs",
1153                     get_tree_code_name (TREE_CODE (t)));
1154   }
1155
1156 private:
1157   /* Implicitly delete any diagnostics in the dtor.  */
1158   auto_delete_vec<pending_diagnostic> m_diagnostics;
1159 };
1160
1161 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1162    Verify that MODEL remains satisfiable.  */
1163
1164 #define ADD_SAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
1165   SELFTEST_BEGIN_STMT                                   \
1166     bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL);     \
1167     ASSERT_TRUE (sat);                                  \
1168   SELFTEST_END_STMT
1169
1170 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1171    Verify that the result is not satisfiable.  */
1172
1173 #define ADD_UNSAT_CONSTRAINT(MODEL, LHS, OP, RHS)       \
1174   SELFTEST_BEGIN_STMT                                   \
1175     bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL);     \
1176     ASSERT_FALSE (sat);                         \
1177   SELFTEST_END_STMT
1178
1179 /* Implementation detail of the ASSERT_CONDITION_* macros.  */
1180
1181 void assert_condition (const location &loc,
1182                        region_model &model,
1183                        const svalue *lhs, tree_code op, const svalue *rhs,
1184                        tristate expected);
1185
1186 void assert_condition (const location &loc,
1187                        region_model &model,
1188                        tree lhs, tree_code op, tree rhs,
1189                        tristate expected);
1190
1191 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1192    as "true".  */
1193
1194 #define ASSERT_CONDITION_TRUE(REGION_MODEL, LHS, OP, RHS) \
1195   SELFTEST_BEGIN_STMT                                                   \
1196   assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,      \
1197                     tristate (tristate::TS_TRUE));              \
1198   SELFTEST_END_STMT
1199
1200 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1201    as "false".  */
1202
1203 #define ASSERT_CONDITION_FALSE(REGION_MODEL, LHS, OP, RHS) \
1204   SELFTEST_BEGIN_STMT                                                   \
1205   assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,      \
1206                     tristate (tristate::TS_FALSE));             \
1207   SELFTEST_END_STMT
1208
1209 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1210    as "unknown".  */
1211
1212 #define ASSERT_CONDITION_UNKNOWN(REGION_MODEL, LHS, OP, RHS) \
1213   SELFTEST_BEGIN_STMT                                                   \
1214   assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,      \
1215                     tristate (tristate::TS_UNKNOWN));           \
1216   SELFTEST_END_STMT
1217
1218 } /* end of namespace selftest.  */
1219
1220 #endif /* #if CHECKING_P */
1221
1222 } // namespace ana
1223
1224 #endif /* GCC_ANALYZER_REGION_MODEL_H */