/* Classes for saving, deduplicating, and emitting analyzer diagnostics.
   Copyright (C) 2019-2020 Free Software Foundation, Inc.
   Contributed by David Malcolm <dmalcolm@redhat.com>.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3, or (at your option)
any later version.

GCC is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.  */

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tree.h"
#include "pretty-print.h"
#include "gcc-rich-location.h"
#include "gimple-pretty-print.h"
#include "function.h"
#include "diagnostic-core.h"
#include "diagnostic-event-id.h"
#include "diagnostic-path.h"
#include "alloc-pool.h"
#include "fibonacci_heap.h"
#include "shortest-paths.h"
#include "sbitmap.h"
#include "tristate.h"
#include "selftest.h"
#include "ordered-hash-map.h"
#include "analyzer/analyzer.h"
#include "analyzer/analyzer-logging.h"
#include "analyzer/sm.h"
#include "analyzer/pending-diagnostic.h"
#include "analyzer/diagnostic-manager.h"
#include "analyzer/region-model.h"
#include "analyzer/constraint-manager.h"
#include "cfg.h"
#include "basic-block.h"
#include "gimple.h"
#include "gimple-iterator.h"
#include "cgraph.h"
#include "digraph.h"
#include "analyzer/supergraph.h"
#include "analyzer/call-string.h"
#include "analyzer/program-point.h"
#include "analyzer/program-state.h"
#include "analyzer/exploded-graph.h"
#include "analyzer/checker-path.h"

#if ENABLE_ANALYZER

namespace ana {

/* class saved_diagnostic.  */

/* saved_diagnostic's ctor.
   Take ownership of D and STMT_FINDER.  */

saved_diagnostic::saved_diagnostic (const state_machine *sm,
				    const exploded_node *enode,
				    const supernode *snode, const gimple *stmt,
				    stmt_finder *stmt_finder,
				    tree var, state_machine::state_t state,
				    pending_diagnostic *d)
: m_sm (sm), m_enode (enode), m_snode (snode), m_stmt (stmt),
 /* stmt_finder could be on-stack; we want our own copy that can
    outlive that.  */
  m_stmt_finder (stmt_finder ? stmt_finder->clone () : NULL),
  m_var (var), m_state (state),
  m_d (d), m_trailing_eedge (NULL)
{
  gcc_assert (m_stmt || m_stmt_finder);

  /* We must have an enode in order to be able to look for paths
     through the exploded_graph to this diagnostic.  */
  gcc_assert (m_enode);
}

/* saved_diagnostic's dtor.  */

saved_diagnostic::~saved_diagnostic ()
{
  delete m_stmt_finder;
  delete m_d;
}

bool
saved_diagnostic::operator== (const saved_diagnostic &other) const
{
  return (m_sm == other.m_sm
	  /* We don't compare m_enode.  */
	  && m_snode == other.m_snode
	  && m_stmt == other.m_stmt
	  /* We don't compare m_stmt_finder.  */
	  && pending_diagnostic::same_tree_p (m_var, other.m_var)
	  && m_state == other.m_state
	  && m_d->equal_p (*other.m_d)
	  && m_trailing_eedge == other.m_trailing_eedge);
}

/* class diagnostic_manager.  */

/* diagnostic_manager's ctor.  */

diagnostic_manager::diagnostic_manager (logger *logger, int verbosity)
: log_user (logger), m_verbosity (verbosity)
{
}

/* Queue pending_diagnostic D at ENODE for later emission.  */

void
diagnostic_manager::add_diagnostic (const state_machine *sm,
				    const exploded_node *enode,
				    const supernode *snode, const gimple *stmt,
				    stmt_finder *finder,
				    tree var, state_machine::state_t state,
				    pending_diagnostic *d)
{
  LOG_FUNC (get_logger ());

  /* We must have an enode in order to be able to look for paths
     through the exploded_graph to the diagnostic.  */
  gcc_assert (enode);

  saved_diagnostic *sd
    = new saved_diagnostic (sm, enode, snode, stmt, finder, var, state, d);
  m_saved_diagnostics.safe_push (sd);
  if (get_logger ())
    log ("adding saved diagnostic %i at SN %i: %qs",
	 m_saved_diagnostics.length () - 1,
	 snode->m_index, d->get_kind ());
}

/* Queue pending_diagnostic D at ENODE for later emission.  */

void
diagnostic_manager::add_diagnostic (const exploded_node *enode,
				    const supernode *snode, const gimple *stmt,
				    stmt_finder *finder,
				    pending_diagnostic *d)
{
  gcc_assert (enode);
  add_diagnostic (NULL, enode, snode, stmt, finder, NULL_TREE, 0, d);
}

/* A class for identifying sets of duplicated pending_diagnostic.

   We want to find the simplest dedupe_candidate amongst those that share a
   dedupe_key.  */

class dedupe_key
{
public:
  dedupe_key (const saved_diagnostic &sd,
	      const exploded_path &epath)
  : m_sd (sd), m_stmt (sd.m_stmt)
  {
    /* Support deferring the choice of stmt until after an emission path has
     been built, using an optional stmt_finder.  */
    if (m_stmt == NULL)
      {
	gcc_assert (sd.m_stmt_finder);
	m_stmt = sd.m_stmt_finder->find_stmt (epath);
      }
    gcc_assert (m_stmt);
  }

  hashval_t hash () const
  {
    inchash::hash hstate;
    hstate.add_ptr (m_stmt);
    // TODO: m_sd
    return hstate.end ();
  }
  bool operator== (const dedupe_key &other) const
  {
    return (m_sd == other.m_sd
	    && m_stmt == other.m_stmt);
  }

  location_t get_location () const
  {
    return m_stmt->location;
  }

  /* A qsort comparator for use by dedupe_winners::emit_best
     to sort them into location_t order.  */

  static int
  comparator (const void *p1, const void *p2)
  {
    const dedupe_key *pk1 = *(const dedupe_key * const *)p1;
    const dedupe_key *pk2 = *(const dedupe_key * const *)p2;

    location_t loc1 = pk1->get_location ();
    location_t loc2 = pk2->get_location ();

    return linemap_compare_locations (line_table, loc2, loc1);
  }

  const saved_diagnostic &m_sd;
  const gimple *m_stmt;
};

/* The value of a slot for a dedupe_key within dedupe_winners:
   the exploded_path for the best candidate for that key, and the
   number of duplicates seen so far.  */

class dedupe_candidate
{
public:
  // has the exploded_path
  dedupe_candidate (const shortest_exploded_paths &sp,
		    const saved_diagnostic &sd)
  : m_epath (sp.get_shortest_path (sd.m_enode)),
    m_num_dupes (0)
  {
  }

  unsigned length () const { return m_epath.length (); }
  const exploded_path &get_path () const { return m_epath; }

  void add_duplicate () { m_num_dupes++; }
  int get_num_dupes () const { return m_num_dupes; }

private:
  exploded_path m_epath;
public:
  int m_num_dupes;
};

/* Traits for use by dedupe_winners.  */

class dedupe_hash_map_traits
{
public:
  typedef const dedupe_key *key_type;
  typedef dedupe_candidate *value_type;
  typedef dedupe_candidate *compare_type;

  static inline hashval_t hash (const key_type &v)
  {
    return v->hash ();
  }
  static inline bool equal_keys (const key_type &k1, const key_type &k2)
  {
    return *k1 == *k2;
  }
  template <typename T>
  static inline void remove (T &)
  {
    // TODO
  }
  template <typename T>
  static inline void mark_deleted (T &entry)
  {
    entry.m_key = reinterpret_cast<key_type> (1);
  }
  template <typename T>
  static inline void mark_empty (T &entry)
  {
    entry.m_key = NULL;
  }
  template <typename T>
  static inline bool is_deleted (const T &entry)
  {
    return entry.m_key == reinterpret_cast<key_type> (1);
  }
  template <typename T>
  static inline bool is_empty (const T &entry)
  {
    return entry.m_key == NULL;
  }
  static const bool empty_zero_p = true;
};

/* A class for deduplicating diagnostics and finding (and emitting) the
   best diagnostic within each partition.  */

class dedupe_winners
{
public:
  ~dedupe_winners ()
  {
    /* Delete all keys and candidates.  */
    for (map_t::iterator iter = m_map.begin ();
	 iter != m_map.end ();
	 ++iter)
      {
	delete (*iter).first;
	delete (*iter).second;
      }
  }

  /* Determine an exploded_path for SD using SP and, if it's feasible,
     determine if it's the best seen so far for its dedupe_key.
     Retain the winner for each dedupe_key, and discard the rest.  */

  void add (logger *logger,
	    const shortest_exploded_paths &sp,
	    const saved_diagnostic &sd)
  {
    /* Build a dedupe_candidate for SD.
       This uses SP to build an exploded_path.  */
    dedupe_candidate *dc = new dedupe_candidate (sp, sd);

    /* Verify that the epath is feasible.
       State-merging means that not every path in the epath corresponds
       to a feasible one w.r.t. states.
       Here we simply check each duplicate saved_diagnostic's
       shortest_path, and reject any that aren't feasible.
       This could introduce false negatives, as there could be longer
       feasible paths within the egraph.  */
    if (logger)
      logger->log ("considering %qs at SN: %i",
		   sd.m_d->get_kind (), sd.m_snode->m_index);
    if (!dc->get_path ().feasible_p (logger))
      {
	if (logger)
	  logger->log ("rejecting %qs at SN: %i"
		       " due to infeasible path",
		       sd.m_d->get_kind (), sd.m_snode->m_index);
	delete dc;
	return;
      }
    else
      if (logger)
	logger->log ("accepting %qs at SN: %i with feasible path",
		     sd.m_d->get_kind (), sd.m_snode->m_index);

    dedupe_key *key = new dedupe_key (sd, dc->get_path ());
    if (dedupe_candidate **slot = m_map.get (key))
      {
	if (logger)
	  logger->log ("already have this dedupe_key");

	(*slot)->add_duplicate ();

	if (dc->length () < (*slot)->length ())
	  {
	    /* We've got a shorter path for the key; replace
	       the current candidate.  */
	    if (logger)
	      logger->log ("length %i is better than existing length %i;"
			   " taking over this dedupe_key",
			   dc->length (), (*slot)->length ());
	    dc->m_num_dupes = (*slot)->get_num_dupes ();
	    delete *slot;
	    *slot = dc;
	  }
	else
	  /* We haven't beaten the current best candidate;
	     drop the new candidate.  */
	  {
	    if (logger)
	      logger->log ("length %i isn't better than existing length %i;"
			   " dropping this candidate",
			   dc->length (), (*slot)->length ());
	    delete dc;
	  }
	delete key;
      }
    else
      {
	/* This is the first candidate for this key.  */
	m_map.put (key, dc);
	if (logger)
	  logger->log ("first candidate for this dedupe_key");
      }
  }

 /* Emit the simplest diagnostic within each set.  */

  void emit_best (diagnostic_manager *dm,
		  const exploded_graph &eg)
  {
    LOG_SCOPE (dm->get_logger ());

    /* Get keys into a vec for sorting.  */
    auto_vec<const dedupe_key *> keys (m_map.elements ());
    for (map_t::iterator iter = m_map.begin ();
	 iter != m_map.end ();
	 ++iter)
      keys.quick_push ((*iter).first);

    dm->log ("# keys after de-duplication: %i", keys.length ());

    /* Sort into a good emission order.  */
    keys.qsort (dedupe_key::comparator);

    /* Emit the best candidate for each key.  */
    int i;
    const dedupe_key *key;
    FOR_EACH_VEC_ELT (keys, i, key)
      {
	dedupe_candidate **slot = m_map.get (key);
	gcc_assert (*slot);
	const dedupe_candidate &dc = **slot;

	dm->emit_saved_diagnostic (eg, key->m_sd,
				   dc.get_path (), key->m_stmt,
				   dc.get_num_dupes ());
      }
  }

private:

  /* This maps from each dedupe_key to a current best dedupe_candidate.  */

  typedef hash_map<const dedupe_key *, dedupe_candidate *,
		   dedupe_hash_map_traits> map_t;
  map_t m_map;
};

/* Emit all saved diagnostics.  */

void
diagnostic_manager::emit_saved_diagnostics (const exploded_graph &eg)
{
  LOG_SCOPE (get_logger ());
  auto_timevar tv (TV_ANALYZER_DIAGNOSTICS);
  log ("# saved diagnostics: %i", m_saved_diagnostics.length ());

  if (m_saved_diagnostics.length () == 0)
    return;

  /* Compute the shortest_paths once, sharing it between all diagnostics.  */
  shortest_exploded_paths sp (eg, eg.get_origin ());

  /* Iterate through all saved diagnostics, adding them to a dedupe_winners
     instance.  This partitions the saved diagnostics by dedupe_key,
     generating exploded_paths for them, and retaining the best one in each
     partition.  */
  dedupe_winners best_candidates;

  int i;
  saved_diagnostic *sd;
  FOR_EACH_VEC_ELT (m_saved_diagnostics, i, sd)
    best_candidates.add (get_logger (), sp, *sd);

  /* For each dedupe-key, call emit_saved_diagnostic on the "best"
     saved_diagnostic.  */
  best_candidates.emit_best (this, eg);
}

/* Given a saved_diagnostic SD at STMT with feasible path EPATH through EG,
   create an checker_path of suitable events and use it to call
   SD's underlying pending_diagnostic "emit" vfunc to emit a diagnostic.  */

void
diagnostic_manager::emit_saved_diagnostic (const exploded_graph &eg,
					   const saved_diagnostic &sd,
					   const exploded_path &epath,
					   const gimple *stmt,
					   int num_dupes)
{
  LOG_SCOPE (get_logger ());
  log ("sd: %qs at SN: %i", sd.m_d->get_kind (), sd.m_snode->m_index);
  log ("num dupes: %i", num_dupes);

  pretty_printer *pp = global_dc->printer->clone ();

  checker_path emission_path;

  /* Populate emission_path with a full description of EPATH.  */
  build_emission_path (eg, epath, &emission_path);

  /* Now prune it to just cover the most pertinent events.  */
  prune_path (&emission_path, sd.m_sm, sd.m_var, sd.m_state);

  /* Add a final event to the path, covering the diagnostic itself.
     We use the final enode from the epath, which might be different from
     the sd.m_enode, as the dedupe code doesn't care about enodes, just
     snodes.  */
  emission_path.add_final_event (sd.m_sm, epath.get_final_enode (), stmt,
				 sd.m_var, sd.m_state);

  /* The "final" event might not be final; if the saved_diagnostic has a
     trailing eedge stashed, add any events for it.  This is for use
     in handling longjmp, to show where a longjmp is rewinding to.  */
  if (sd.m_trailing_eedge)
    add_events_for_eedge (*sd.m_trailing_eedge, eg.get_ext_state (),
			  &emission_path);

  emission_path.prepare_for_emission (sd.m_d);

  gcc_rich_location rich_loc (stmt->location);
  rich_loc.set_path (&emission_path);

  auto_diagnostic_group d;
  auto_cfun sentinel (sd.m_snode->m_fun);
  if (sd.m_d->emit (&rich_loc))
    {
      if (num_dupes > 0)
	inform_n (stmt->location, num_dupes,
		  "%i duplicate", "%i duplicates",
		  num_dupes);
    }
  delete pp;
}

/* Given a state change to DST_REP, determine a tree that gives the origin
   of that state at STMT, using DST_STATE's region model, so that state
   changes based on assignments can be tracked back to their origins.

   For example, if we have

     (S1) _1 = malloc (64);
     (S2) EXPR = _1;

   then at stmt S2 we can get the origin of EXPR's state as being _1,
   and thus track the allocation back to S1.  */

static tree
get_any_origin (const gimple *stmt,
		tree dst_rep,
		const program_state &dst_state)
{
  if (!stmt)
    return NULL_TREE;

  gcc_assert (dst_rep);

  if (const gassign *assign = dyn_cast <const gassign *> (stmt))
    {
      tree lhs = gimple_assign_lhs (assign);
      /* Use region IDs to compare lhs with DST_REP.  */
      if (dst_state.m_region_model->get_lvalue (lhs, NULL)
	  == dst_state.m_region_model->get_lvalue (dst_rep, NULL))
	{
	  tree rhs1 = gimple_assign_rhs1 (assign);
	  enum tree_code op = gimple_assign_rhs_code (assign);
	  switch (op)
	    {
	    default:
	      //gcc_unreachable ();  // TODO
	      break;
	    case COMPONENT_REF:
	    case SSA_NAME:
	      return rhs1;
	    }
	}
    }
  return NULL_TREE;
}

/* Emit a "path" of events to EMISSION_PATH describing the exploded path
   EPATH within EG.  */

void
diagnostic_manager::build_emission_path (const exploded_graph &eg,
					 const exploded_path &epath,
					 checker_path *emission_path) const
{
  LOG_SCOPE (get_logger ());
  const extrinsic_state &ext_state = eg.get_ext_state ();
  for (unsigned i = 0; i < epath.m_edges.length (); i++)
    {
      const exploded_edge *eedge = epath.m_edges[i];
      add_events_for_eedge (*eedge, ext_state, emission_path);
    }
}

/* Subclass of state_change_visitor that creates state_change_event
   instances.  */

class state_change_event_creator : public state_change_visitor
{
public:
  state_change_event_creator (const exploded_edge &eedge,
			      checker_path *emission_path)
    : m_eedge (eedge),
      m_emission_path (emission_path)
  {}

  bool on_global_state_change (const state_machine &sm,
			       state_machine::state_t src_sm_val,
			       state_machine::state_t dst_sm_val)
    FINAL OVERRIDE
  {
    const exploded_node *src_node = m_eedge.m_src;
    const program_point &src_point = src_node->get_point ();
    const int src_stack_depth = src_point.get_stack_depth ();
    const exploded_node *dst_node = m_eedge.m_dest;
    const gimple *stmt = src_point.get_stmt ();
    const supernode *supernode = src_point.get_supernode ();
    const program_state &dst_state = dst_node->get_state ();

    int stack_depth = src_stack_depth;

    m_emission_path->add_event (new state_change_event (supernode,
							stmt,
							stack_depth,
							sm,
							NULL_TREE,
							src_sm_val,
							dst_sm_val,
							NULL_TREE,
							dst_state));
    return false;
  }

  bool on_state_change (const state_machine &sm,
			state_machine::state_t src_sm_val,
			state_machine::state_t dst_sm_val,
			tree dst_rep,
			svalue_id dst_origin_sid) FINAL OVERRIDE
  {
    const exploded_node *src_node = m_eedge.m_src;
    const program_point &src_point = src_node->get_point ();
    const int src_stack_depth = src_point.get_stack_depth ();
    const exploded_node *dst_node = m_eedge.m_dest;
    const gimple *stmt = src_point.get_stmt ();
    const supernode *supernode = src_point.get_supernode ();
    const program_state &dst_state = dst_node->get_state ();

    int stack_depth = src_stack_depth;

    if (m_eedge.m_sedge
	&& m_eedge.m_sedge->m_kind == SUPEREDGE_CFG_EDGE)
      {
	supernode = src_point.get_supernode ();
	stmt = supernode->get_last_stmt ();
	stack_depth = src_stack_depth;
      }

    /* Bulletproofing for state changes at calls/returns;
       TODO: is there a better way? */
    if (!stmt)
      return false;

    tree origin_rep
      = dst_state.get_representative_tree (dst_origin_sid);

    if (origin_rep == NULL_TREE)
      origin_rep = get_any_origin (stmt, dst_rep, dst_state);
    m_emission_path->add_event (new state_change_event (supernode,
							stmt,
							stack_depth,
							sm,
							dst_rep,
							src_sm_val,
							dst_sm_val,
							origin_rep,
							dst_state));
    return false;
  }

  const exploded_edge &m_eedge;
  checker_path *m_emission_path;
};

/* Compare SRC_STATE and DST_STATE (which use EXT_STATE), and call
   VISITOR's on_state_change for every sm-state change that occurs
   to a tree, and on_global_state_change for every global state change
   that occurs.

   This determines the state changes that ought to be reported to
   the user: a combination of the effects of changes to sm_state_map
   (which maps svalues to sm-states), and of region_model changes
   (which map trees to svalues).

   Bail out early and return true if any call to on_global_state_change
   or on_state_change returns true, otherwise return false.

   This is split out to make it easier to experiment with changes to
   exploded_node granularity (so that we can observe what state changes
   lead to state_change_events being emitted).  */

bool
for_each_state_change (const program_state &src_state,
		       const program_state &dst_state,
		       const extrinsic_state &ext_state,
		       state_change_visitor *visitor)
{
  gcc_assert (src_state.m_checker_states.length ()
	      == ext_state.get_num_checkers ());
  gcc_assert (dst_state.m_checker_states.length ()
	      == ext_state.get_num_checkers ());
  for (unsigned i = 0; i < ext_state.get_num_checkers (); i++)
    {
      const state_machine &sm = ext_state.get_sm (i);
      const sm_state_map &src_smap = *src_state.m_checker_states[i];
      const sm_state_map &dst_smap = *dst_state.m_checker_states[i];

      /* Add events for any global state changes.  */
      if (src_smap.get_global_state () != dst_smap.get_global_state ())
	if (visitor->on_global_state_change (sm,
					     src_smap.get_global_state (),
					     dst_smap.get_global_state ()))
	  return true;

      /* Add events for per-svalue state changes.  */
      for (sm_state_map::iterator_t iter = dst_smap.begin ();
	   iter != dst_smap.end ();
	   ++iter)
	{
	  /* Ideally we'd directly compare the SM state between src state
	     and dst state, but there's no guarantee that the IDs can
	     be meaningfully compared.  */
	  svalue_id dst_sid = (*iter).first;
	  state_machine::state_t dst_sm_val = (*iter).second.m_state;

	  auto_vec<path_var> dst_pvs;
	  dst_state.m_region_model->get_path_vars_for_svalue (dst_sid,
							      &dst_pvs);

	  unsigned j;
	  path_var *dst_pv;
	  FOR_EACH_VEC_ELT (dst_pvs, j, dst_pv)
	    {
	      tree dst_rep = dst_pv->m_tree;
	      gcc_assert (dst_rep);
	      if (dst_pv->m_stack_depth
		  >= src_state.m_region_model->get_stack_depth ())
		continue;
	      svalue_id src_sid
		= src_state.m_region_model->get_rvalue (*dst_pv, NULL);
	      if (src_sid.null_p ())
		continue;
	      state_machine::state_t src_sm_val = src_smap.get_state (src_sid);
	      if (dst_sm_val != src_sm_val)
		{
		  svalue_id dst_origin_sid = (*iter).second.m_origin;
		  if (visitor->on_state_change (sm, src_sm_val, dst_sm_val,
						dst_rep, dst_origin_sid))
		    return true;
		}
	    }
	}
    }
  return false;
}

/* Subroutine of diagnostic_manager::build_emission_path.
   Add any events for EEDGE to EMISSION_PATH.  */

void
diagnostic_manager::add_events_for_eedge (const exploded_edge &eedge,
					  const extrinsic_state &ext_state,
					  checker_path *emission_path) const
{
  const exploded_node *src_node = eedge.m_src;
  const program_point &src_point = src_node->get_point ();
  const exploded_node *dst_node = eedge.m_dest;
  const program_point &dst_point = dst_node->get_point ();
  const int dst_stack_depth = dst_point.get_stack_depth ();
  if (get_logger ())
    {
      get_logger ()->start_log_line ();
      pretty_printer *pp = get_logger ()->get_printer ();
      pp_printf (pp, "EN %i -> EN %i: ",
		 eedge.m_src->m_index,
		 eedge.m_dest->m_index);
      src_point.print (pp, format (false));
      pp_string (pp, "-> ");
      dst_point.print (pp, format (false));
      get_logger ()->end_log_line ();
    }
  const program_state &src_state = src_node->get_state ();
  const program_state &dst_state = dst_node->get_state ();

  /* Add state change events for the states that have changed.
     We add these before events for superedges, so that if we have a
     state_change_event due to following an edge, we'll get this sequence
     of events:

      | if (!ptr)
      |    ~
      |    |
      |    (1) assuming 'ptr' is non-NULL  (state_change_event)
      |    (2) following 'false' branch... (start_cfg_edge_event)
     ...
      | do_something (ptr);
      | ~~~~~~~~~~~~~^~~~~
      |              |
      |              (3) ...to here        (end_cfg_edge_event).  */
  state_change_event_creator visitor (eedge, emission_path);
  for_each_state_change (src_state, dst_state, ext_state,
			 &visitor);

  /* Allow non-standard edges to add events, e.g. when rewinding from
     longjmp to a setjmp.  */
  if (eedge.m_custom_info)
    eedge.m_custom_info->add_events_to_path (emission_path, eedge);

  /* Add events for superedges, function entries, and for statements.  */
  switch (dst_point.get_kind ())
    {
    default:
      break;
    case PK_BEFORE_SUPERNODE:
      if (src_point.get_kind () == PK_AFTER_SUPERNODE)
	{
	  if (eedge.m_sedge)
	    add_events_for_superedge (eedge, emission_path);
	}
      /* Add function entry events.  */
      if (dst_point.get_supernode ()->entry_p ())
	{
	  emission_path->add_event
	    (new function_entry_event
	     (dst_point.get_supernode ()->get_start_location (),
	      dst_point.get_fndecl (),
	      dst_stack_depth));
	}
      break;
    case PK_BEFORE_STMT:
      {
	const gimple *stmt = dst_point.get_stmt ();
	const gcall *call = dyn_cast <const gcall *> (stmt);
	if (call && is_setjmp_call_p (call))
	  emission_path->add_event
	    (new setjmp_event (stmt->location,
			       dst_node,
			       dst_point.get_fndecl (),
			       dst_stack_depth,
			       call));
	else
	  emission_path->add_event
	    (new statement_event (stmt,
				  dst_point.get_fndecl (),
				  dst_stack_depth, dst_state));
      }
      break;
    }
}

/* Subroutine of diagnostic_manager::add_events_for_eedge
   where EEDGE has an underlying superedge i.e. a CFG edge,
   or an interprocedural call/return.
   Add any events for the superedge to EMISSION_PATH.  */

void
diagnostic_manager::add_events_for_superedge (const exploded_edge &eedge,
					      checker_path *emission_path)
  const
{
  gcc_assert (eedge.m_sedge);

  const exploded_node *src_node = eedge.m_src;
  const program_point &src_point = src_node->get_point ();
  const exploded_node *dst_node = eedge.m_dest;
  const program_point &dst_point = dst_node->get_point ();
  const int src_stack_depth = src_point.get_stack_depth ();
  const int dst_stack_depth = dst_point.get_stack_depth ();
  const gimple *last_stmt = src_point.get_supernode ()->get_last_stmt ();

  switch (eedge.m_sedge->m_kind)
    {
    case SUPEREDGE_CFG_EDGE:
      {
	emission_path->add_event
	  (new start_cfg_edge_event (eedge,
			       (last_stmt
				? last_stmt->location
				: UNKNOWN_LOCATION),
			       src_point.get_fndecl (),
			       src_stack_depth));
	emission_path->add_event
	  (new end_cfg_edge_event (eedge,
				   dst_point.get_supernode ()->get_start_location (),
				   dst_point.get_fndecl (),
				   dst_stack_depth));
      }
      break;

    case SUPEREDGE_CALL:
      {
	emission_path->add_event
	  (new call_event (eedge,
			   (last_stmt
			    ? last_stmt->location
			    : UNKNOWN_LOCATION),
			   src_point.get_fndecl (),
			   src_stack_depth));
      }
      break;

    case SUPEREDGE_INTRAPROCEDURAL_CALL:
      {
	/* TODO: add a subclass for this, or generate events for the
	   summary.  */
	emission_path->add_event
	  (new debug_event ((last_stmt
			     ? last_stmt->location
			     : UNKNOWN_LOCATION),
			    src_point.get_fndecl (),
			    src_stack_depth,
			    "call summary"));
      }
      break;

    case SUPEREDGE_RETURN:
      {
	const return_superedge *return_edge
	  = as_a <const return_superedge *> (eedge.m_sedge);

	const gcall *call_stmt = return_edge->get_call_stmt ();
	emission_path->add_event
	  (new return_event (eedge,
			     (call_stmt
			      ? call_stmt->location
			      : UNKNOWN_LOCATION),
			     dst_point.get_fndecl (),
			     dst_stack_depth));
      }
      break;
    }
}

/* Prune PATH, based on the verbosity level, to the most pertinent
   events for a diagnostic that involves VAR ending in state STATE
   (for state machine SM).

   PATH is updated in place, and the redundant checker_events are deleted.

   As well as deleting events, call record_critical_state on events in
   which state critical to the pending_diagnostic is being handled; see
   the comment for diagnostic_manager::prune_for_sm_diagnostic.  */

void
diagnostic_manager::prune_path (checker_path *path,
				const state_machine *sm,
				tree var,
				state_machine::state_t state) const
{
  LOG_FUNC (get_logger ());
  path->maybe_log (get_logger (), "path");
  prune_for_sm_diagnostic (path, sm, var, state);
  prune_interproc_events (path);
  finish_pruning (path);
  path->maybe_log (get_logger (), "pruned");
}

/* First pass of diagnostic_manager::prune_path: apply verbosity level,
   pruning unrelated state change events.

   Iterate backwards through PATH, skipping state change events that aren't
   VAR but update the pertinent VAR when state-copying occurs.

   As well as deleting events, call record_critical_state on events in
   which state critical to the pending_diagnostic is being handled, so
   that the event's get_desc vfunc can potentially supply a more precise
   description of the event to the user.
   e.g. improving
     "calling 'foo' from 'bar'"
   to
     "passing possibly-NULL pointer 'ptr' to 'foo' from 'bar' as param 1"
   when the diagnostic relates to later dereferencing 'ptr'.  */

void
diagnostic_manager::prune_for_sm_diagnostic (checker_path *path,
					     const state_machine *sm,
					     tree var,
					     state_machine::state_t state) const
{
  /* If we have a constant (such as NULL), assume its state is also
     constant, so as not to attempt to get its lvalue whilst tracking the
     origin of the state.  */
  if (var && CONSTANT_CLASS_P (var))
    var = NULL_TREE;

  int idx = path->num_events () - 1;
  while (idx >= 0 && idx < (signed)path->num_events ())
    {
      checker_event *base_event = path->get_checker_event (idx);
      if (get_logger ())
	{
	  if (sm)
	    {
	      if (var)
		log ("considering event %i, with var: %qE, state: %qs",
		     idx, var, sm->get_state_name (state));
	      else
		log ("considering event %i, with global state: %qs",
		     idx, sm->get_state_name (state));
	    }
	  else
	    log ("considering event %i", idx);
	}
      switch (base_event->m_kind)
	{
	default:
	  gcc_unreachable ();

	case EK_DEBUG:
	  if (m_verbosity < 3)
	    {
	      log ("filtering event %i: debug event", idx);
	      path->delete_event (idx);
	    }
	  break;

	case EK_CUSTOM:
	  /* Don't filter custom events.  */
	  break;

	case EK_STMT:
	  {
	    /* If this stmt is the origin of "var", update var.  */
	    if (var)
	      {
		statement_event *stmt_event = (statement_event *)base_event;
		tree new_var = get_any_origin (stmt_event->m_stmt, var,
					       stmt_event->m_dst_state);
		if (new_var)
		  {
		    log ("event %i: switching var of interest from %qE to %qE",
			 idx, var, new_var);
		    var = new_var;
		  }
	      }
	    if (m_verbosity < 3)
	      {
		log ("filtering event %i: statement event", idx);
		path->delete_event (idx);
	      }
	  }
	  break;

	case EK_FUNCTION_ENTRY:
	  if (m_verbosity < 1)
	    {
	      log ("filtering event %i: function entry", idx);
	      path->delete_event (idx);
	    }
	  break;

	case EK_STATE_CHANGE:
	  {
	    state_change_event *state_change = (state_change_event *)base_event;
	    if (state_change->get_lvalue (state_change->m_var)
		== state_change->get_lvalue (var))
	      {
		if (state_change->m_origin)
		  {
		    log ("event %i: switching var of interest from %qE to %qE",
			 idx, var, state_change->m_origin);
		    var = state_change->m_origin;
		  }
		log ("event %i: switching state of interest from %qs to %qs",
		     idx, sm->get_state_name (state_change->m_to),
		     sm->get_state_name (state_change->m_from));
		state = state_change->m_from;
	      }
	    else if (m_verbosity < 3)
	      {
		if (var)
		  log ("filtering event %i:"
		       " state change to %qE unrelated to %qE",
		       idx, state_change->m_var, var);
		else
		  log ("filtering event %i: state change to %qE",
		       idx, state_change->m_var);
		path->delete_event (idx);
	      }
	  }
	  break;

	case EK_START_CFG_EDGE:
	  {
	    cfg_edge_event *event = (cfg_edge_event *)base_event;
	    const cfg_superedge& cfg_superedge
	      = event->get_cfg_superedge ();
	    const supernode *dest = event->m_sedge->m_dest;
	    /* Do we have an SSA_NAME defined via a phi node in
	       the dest CFG node?  */
	    if (var && TREE_CODE (var) == SSA_NAME)
	      if (SSA_NAME_DEF_STMT (var)->bb == dest->m_bb)
		{
		  if (gphi *phi
		      = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (var)))
		    {
		      /* Update var based on its phi node.  */
		      tree old_var = var;
		      var = cfg_superedge.get_phi_arg (phi);
		      log ("updating from %qE to %qE based on phi node",
			   old_var, var);
		      if (get_logger ())
			{
			  pretty_printer pp;
			  pp_gimple_stmt_1 (&pp, phi, 0, (dump_flags_t)0);
			  log ("  phi: %s", pp_formatted_text (&pp));
			}
		      /* If we've chosen a bad exploded_path, then the
			 phi arg might be a constant.  Fail gracefully for
			 this case.  */
		      if (CONSTANT_CLASS_P (var))
			{
			  log ("new var is a constant (bad path?);"
			       " setting var to NULL");
			  var = NULL;
			}
		    }
		}

	    /* TODO: is this edge significant to var?
	       See if var can be in other states in the dest, but not
	       in other states in the src?
	       Must have multiple sibling edges.  */

	    if (event->should_filter_p (m_verbosity))
	      {
		log ("filtering event %i: CFG edge", idx);
		path->delete_event (idx);
		/* Also delete the corresponding EK_END_CFG_EDGE.  */
		gcc_assert (path->get_checker_event (idx)->m_kind
			    == EK_END_CFG_EDGE);
		path->delete_event (idx);
	      }
	  }
	  break;

	case EK_END_CFG_EDGE:
	  /* These come in pairs with EK_START_CFG_EDGE events and are
	     filtered when their start event is filtered.  */
	  break;

	case EK_CALL_EDGE:
	  {
	    call_event *event = (call_event *)base_event;
	    const callgraph_superedge& cg_superedge
	      = event->get_callgraph_superedge ();
	    callsite_expr expr;
	    tree caller_var
	      = cg_superedge.map_expr_from_callee_to_caller (var, &expr);
	    if (caller_var)
	      {
		log ("event %i:"
		     " switching var of interest"
		     " from %qE in callee to %qE in caller",
		     idx, var, caller_var);
		var = caller_var;
		if (expr.param_p ())
		  event->record_critical_state (var, state);
	      }
	  }
	  break;

	case EK_RETURN_EDGE:
	  // TODO: potentially update var/state based on return value,
	  // args etc
	  {
	    if (var)
	      {
		return_event *event = (return_event *)base_event;
		const callgraph_superedge& cg_superedge
		  = event->get_callgraph_superedge ();
		callsite_expr expr;
		tree callee_var
		  = cg_superedge.map_expr_from_caller_to_callee (var, &expr);
		if (callee_var)
		  {
		    log ("event %i:"
			 " switching var of interest"
			 " from %qE in caller to %qE in callee",
			 idx, var, callee_var);
		    var = callee_var;
		    if (expr.return_value_p ())
		      event->record_critical_state (var, state);
		  }
	      }
	  }
	  break;

	case EK_SETJMP:
	  /* TODO: only show setjmp_events that matter i.e. those for which
	     there is a later rewind event using them.  */
	case EK_REWIND_FROM_LONGJMP:
	case EK_REWIND_TO_SETJMP:
	  break;

	case EK_WARNING:
	  /* Always show the final "warning" event in the path.  */
	  break;
	}
      idx--;
    }
}

/* Second pass of diagnostic_manager::prune_path: remove redundant
   interprocedural information.

   For example, given:
     (1)- calling "f2" from "f1"
     (2)--- entry to "f2"
     (3)--- calling "f3" from "f2"
     (4)----- entry to "f3"
     (5)--- returning to "f2" to "f3"
     (6)- returning to "f1" to "f2"
   with no other intervening events, then none of these events are
   likely to be interesting to the user.

   Prune [..., call, function-entry, return, ...] triples repeatedly
   until nothing has changed.  For the example above, this would
   remove events (3, 4, 5), and then remove events (1, 2, 6).  */

void
diagnostic_manager::prune_interproc_events (checker_path *path) const
{
  bool changed = false;
  do
    {
      changed = false;
      int idx = path->num_events () - 1;
      while (idx >= 0)
	{
	  /* Prune [..., call, function-entry, return, ...] triples.  */
	  if (idx + 2 < (signed)path->num_events ()
	      && path->get_checker_event (idx)->is_call_p ()
	      && path->get_checker_event (idx + 1)->is_function_entry_p ()
	      && path->get_checker_event (idx + 2)->is_return_p ())
	    {
	      if (get_logger ())
		{
		  label_text desc
		    (path->get_checker_event (idx)->get_desc (false));
		  log ("filtering events %i-%i:"
		       " irrelevant call/entry/return: %s",
		       idx, idx + 2, desc.m_buffer);
		  desc.maybe_free ();
		}
	      path->delete_event (idx + 2);
	      path->delete_event (idx + 1);
	      path->delete_event (idx);
	      changed = true;
	      idx--;
	      continue;
	    }

	  /* Prune [..., call, return, ...] pairs
	     (for -fanalyzer-verbosity=0).  */
	  if (idx + 1 < (signed)path->num_events ()
	      && path->get_checker_event (idx)->is_call_p ()
	      && path->get_checker_event (idx + 1)->is_return_p ())
	    {
	      if (get_logger ())
		{
		  label_text desc
		    (path->get_checker_event (idx)->get_desc (false));
		  log ("filtering events %i-%i:"
		       " irrelevant call/return: %s",
		       idx, idx + 1, desc.m_buffer);
		  desc.maybe_free ();
		}
	      path->delete_event (idx + 1);
	      path->delete_event (idx);
	      changed = true;
	      idx--;
	      continue;
	    }

	  idx--;
	}

    }
  while (changed);
}

/* Final pass of diagnostic_manager::prune_path.

   If all we're left with is in one function, then filter function entry
   events.  */

void
diagnostic_manager::finish_pruning (checker_path *path) const
{
  if (!path->interprocedural_p ())
    {
      int idx = path->num_events () - 1;
      while (idx >= 0 && idx < (signed)path->num_events ())
	{
	  checker_event *base_event = path->get_checker_event (idx);
	  if (base_event->m_kind == EK_FUNCTION_ENTRY)
	    {
	      log ("filtering event %i:"
		   " function entry for purely intraprocedural path", idx);
	      path->delete_event (idx);
	    }
	  idx--;
	}
    }
}

} // namespace ana

#endif /* #if ENABLE_ANALYZER */