/* Classes for representing locations within the program.
   Copyright (C) 2019-2022 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 "gimple-pretty-print.h"
#include "gcc-rich-location.h"
#include "json.h"
#include "ordered-hash-map.h"
#include "options.h"
#include "cgraph.h"
#include "function.h"
#include "cfg.h"
#include "basic-block.h"
#include "gimple.h"
#include "gimple-iterator.h"
#include "digraph.h"
#include "analyzer/analyzer.h"
#include "analyzer/analyzer-logging.h"
#include "analyzer/call-string.h"
#include "analyzer/supergraph.h"
#include "analyzer/program-point.h"
#include "sbitmap.h"
#include "bitmap.h"
#include "tristate.h"
#include "selftest.h"
#include "analyzer/store.h"
#include "analyzer/region-model.h"
#include "analyzer/sm.h"
#include "analyzer/program-state.h"
#include "alloc-pool.h"
#include "fibonacci_heap.h"
#include "diagnostic-event-id.h"
#include "analyzer/pending-diagnostic.h"
#include "analyzer/diagnostic-manager.h"
#include "shortest-paths.h"
#include "analyzer/exploded-graph.h"
#include "analyzer/analysis-plan.h"

#if ENABLE_ANALYZER

namespace ana {

/* Get a string for PK.  */

const char *
point_kind_to_string (enum point_kind pk)
{
  switch (pk)
    {
    default:
      gcc_unreachable ();
    case PK_ORIGIN:
      return "PK_ORIGIN";
    case PK_BEFORE_SUPERNODE:
      return "PK_BEFORE_SUPERNODE";
    case PK_BEFORE_STMT:
      return "PK_BEFORE_STMT";
    case PK_AFTER_SUPERNODE:
      return "PK_AFTER_SUPERNODE";
    case PK_EMPTY:
      return "PK_EMPTY";
    case PK_DELETED:
      return "PK_DELETED";
    }
}

/* class function_point.  */

function_point::function_point (const supernode *supernode,
				const superedge *from_edge,
				unsigned stmt_idx,
				enum point_kind kind)
: m_supernode (supernode), m_from_edge (from_edge),
  m_stmt_idx (stmt_idx), m_kind (kind)
{
  if (from_edge)
    {
      gcc_checking_assert (m_kind == PK_BEFORE_SUPERNODE);
      gcc_checking_assert (from_edge->get_kind () == SUPEREDGE_CFG_EDGE);
    }
  if (stmt_idx)
    gcc_checking_assert (m_kind == PK_BEFORE_STMT);
}

/* Print this function_point to PP.  */

void
function_point::print (pretty_printer *pp, const format &f) const
{
  switch (get_kind ())
    {
    default:
      gcc_unreachable ();

    case PK_ORIGIN:
      pp_printf (pp, "origin");
      if (f.m_newlines)
	pp_newline (pp);
      break;

    case PK_BEFORE_SUPERNODE:
      {
	if (m_from_edge)
	  {
	    if (basic_block bb = m_from_edge->m_src->m_bb)
	      pp_printf (pp, "before SN: %i (from SN: %i (bb: %i))",
			 m_supernode->m_index, m_from_edge->m_src->m_index,
			 bb->index);
	    else
	      pp_printf (pp, "before SN: %i (from SN: %i)",
			 m_supernode->m_index, m_from_edge->m_src->m_index);
	  }
	else
	  pp_printf (pp, "before SN: %i (NULL from-edge)",
		     m_supernode->m_index);
	f.spacer (pp);
	for (gphi_iterator gpi
	       = const_cast<supernode *>(get_supernode ())->start_phis ();
	     !gsi_end_p (gpi); gsi_next (&gpi))
	  {
	    const gphi *phi = gpi.phi ();
	    pp_gimple_stmt_1 (pp, phi, 0, (dump_flags_t)0);
	  }
      }
      break;

    case PK_BEFORE_STMT:
      pp_printf (pp, "before (SN: %i stmt: %i): ", m_supernode->m_index,
		 m_stmt_idx);
      f.spacer (pp);
      pp_gimple_stmt_1 (pp, get_stmt (), 0, (dump_flags_t)0);
      if (f.m_newlines)
	{
	  pp_newline (pp);
	  print_source_line (pp);
	}
      break;

    case PK_AFTER_SUPERNODE:
      pp_printf (pp, "after SN: %i", m_supernode->m_index);
      if (f.m_newlines)
	pp_newline (pp);
      break;
    }
}

/* Generate a hash value for this function_point.  */

hashval_t
function_point::hash () const
{
  inchash::hash hstate;
  if (m_supernode)
    hstate.add_int (m_supernode->m_index);
  hstate.add_ptr (m_from_edge);
  hstate.add_int (m_stmt_idx);
  hstate.add_int (m_kind);
  return hstate.end ();
}

/* Get the function at this point, if any.  */

function *
function_point::get_function () const
{
  if (m_supernode)
    return m_supernode->m_fun;
  else
    return NULL;
}

/* Get the gimple stmt for this function_point, if any.  */

const gimple *
function_point::get_stmt () const
{
  if (m_kind == PK_BEFORE_STMT)
    return m_supernode->m_stmts[m_stmt_idx];
  else if (m_kind == PK_AFTER_SUPERNODE)
    return m_supernode->get_last_stmt ();
  else
    return NULL;
}

/* Get a location for this function_point, if any.  */

location_t
function_point::get_location () const
{
  const gimple *stmt = get_stmt ();
  if (stmt)
    return stmt->location;
  if (m_kind == PK_BEFORE_SUPERNODE)
    return m_supernode->get_start_location ();
  else if (m_kind == PK_AFTER_SUPERNODE)
    return m_supernode->get_end_location ();
  else
    return UNKNOWN_LOCATION;
}

/* Return true if this function_point is a before_stmt for
   the final stmt in its supernode.  */

bool
function_point::final_stmt_p () const
{
  if (m_kind != PK_BEFORE_STMT)
    return false;
  return m_stmt_idx == get_supernode ()->m_stmts.length () - 1;
}

/* Create a function_point representing the entrypoint of function FUN.  */

function_point
function_point::from_function_entry (const supergraph &sg, function *fun)
{
  return before_supernode (sg.get_node_for_function_entry (fun), NULL);
}

/* Create a function_point representing entering supernode SUPERNODE,
   having reached it via FROM_EDGE (which could be NULL).  */

function_point
function_point::before_supernode (const supernode *supernode,
				  const superedge *from_edge)
{
  if (from_edge && from_edge->get_kind () != SUPEREDGE_CFG_EDGE)
    from_edge = NULL;
  return function_point (supernode, from_edge, 0, PK_BEFORE_SUPERNODE);
}

/* A subclass of diagnostic_context for use by
   program_point::print_source_line.  */

class debug_diagnostic_context : public diagnostic_context
{
public:
  debug_diagnostic_context ()
  {
    diagnostic_initialize (this, 0);
    show_line_numbers_p = true;
    show_caret = true;
  }
  ~debug_diagnostic_context ()
  {
    diagnostic_finish (this);
  }
};

/* Print the source line (if any) for this function_point to PP.  */

void
function_point::print_source_line (pretty_printer *pp) const
{
  const gimple *stmt = get_stmt ();
  if (!stmt)
    return;
  // TODO: monospace font
  debug_diagnostic_context tmp_dc;
  gcc_rich_location richloc (stmt->location);
  diagnostic_show_locus (&tmp_dc, &richloc, DK_ERROR);
  pp_string (pp, pp_formatted_text (tmp_dc.printer));
}

/* class program_point.  */

/* Print this program_point to PP.  */

void
program_point::print (pretty_printer *pp, const format &f) const
{
  pp_string (pp, "callstring: ");
  m_call_string->print (pp);
  f.spacer (pp);

  m_function_point.print (pp, f);
}

/* Dump this point to stderr.  */

DEBUG_FUNCTION void
program_point::dump () const
{
  pretty_printer pp;
  pp_show_color (&pp) = pp_show_color (global_dc->printer);
  pp.buffer->stream = stderr;
  print (&pp, format (true));
  pp_flush (&pp);
}

/* Return a new json::object of the form
   {"kind"  : str,
    "snode_idx" : int (optional), the index of the supernode,
    "from_edge_snode_idx" : int (only for kind=='PK_BEFORE_SUPERNODE'),
    "stmt_idx": int (only for kind=='PK_BEFORE_STMT',
    "call_string": object for the call_string}.  */

json::object *
program_point::to_json () const
{
  json::object *point_obj = new json::object ();

  point_obj->set ("kind",
		  new json::string (point_kind_to_string (get_kind ())));

  if (get_supernode ())
    point_obj->set ("snode_idx",
		    new json::integer_number (get_supernode ()->m_index));

  switch (get_kind ())
    {
    default: break;
    case PK_BEFORE_SUPERNODE:
      if (const superedge *sedge = get_from_edge ())
	point_obj->set ("from_edge_snode_idx",
			new json::integer_number (sedge->m_src->m_index));
      break;
    case PK_BEFORE_STMT:
      point_obj->set ("stmt_idx", new json::integer_number (get_stmt_idx ()));
      break;
    }

  point_obj->set ("call_string", m_call_string->to_json ());

  return point_obj;
}

/* Update the callstack to represent a call from caller to callee.

   Generally used to push a custom call to a perticular program point 
   where we don't have a superedge representing the call.  */
void
program_point::push_to_call_stack (const supernode *caller,
				   const supernode *callee)
{
  m_call_string = m_call_string->push_call (callee, caller);
}

/* Pop the topmost call from the current callstack.  */
void
program_point::pop_from_call_stack ()
{
  m_call_string = m_call_string->get_parent ();
  gcc_assert (m_call_string);
}

/* Generate a hash value for this program_point.  */

hashval_t
program_point::hash () const
{
  inchash::hash hstate;
  hstate.merge_hash (m_function_point.hash ());
  hstate.add_ptr (m_call_string);
  return hstate.end ();
}

/* Get the function * at DEPTH within the call stack.  */

function *
program_point::get_function_at_depth (unsigned depth) const
{
  gcc_assert (depth <= m_call_string->length ());
  if (depth == m_call_string->length ())
    return m_function_point.get_function ();
  else
    return get_call_string ()[depth].get_caller_function ();
}

/* Assert that this object is sane.  */

void
program_point::validate () const
{
  /* Skip this in a release build.  */
#if !CHECKING_P
  return;
#endif

  m_call_string->validate ();
  /* The "callee" of the final entry in the callstring should be the
     function of the m_function_point.  */
  if (m_call_string->length () > 0)
    gcc_assert
      ((*m_call_string)[m_call_string->length () - 1].get_callee_function ()
       == get_function ());
}

/* Check to see if SUCC is a valid edge to take (ensuring that we have
   interprocedurally valid paths in the exploded graph, and enforcing
   recursion limits).

   Update the call string if SUCC is a call or a return.

   Return true if SUCC can be taken, or false otherwise.

   This is the "point" half of exploded_node::on_edge.  */

bool
program_point::on_edge (exploded_graph &eg,
			const superedge *succ)
{
  logger * const logger = eg.get_logger ();
  LOG_FUNC (logger);
  switch (succ->m_kind)
    {
    case SUPEREDGE_CFG_EDGE:
      {
	const cfg_superedge *cfg_sedge = as_a <const cfg_superedge *> (succ);

	/* Reject abnormal edges; we special-case setjmp/longjmp.  */
	if (cfg_sedge->get_flags () & EDGE_ABNORMAL)
	  return false;
      }
      break;

    case SUPEREDGE_CALL:
      {
	const call_superedge *call_sedge = as_a <const call_superedge *> (succ);

	if (eg.get_analysis_plan ().use_summary_p (call_sedge->m_cedge))
	  {
	    if (logger)
	      logger->log ("rejecting call edge: using summary instead");
	    return false;
	  }

	/* Add the callsite to the call string.  */
	m_call_string = m_call_string->push_call (eg.get_supergraph (),
						  call_sedge);

	/* Impose a maximum recursion depth and don't analyze paths
	   that exceed it further.
	   This is something of a blunt workaround, but it only
	   applies to recursion (and mutual recursion), not to
	   general call stacks.  */
	if (m_call_string->calc_recursion_depth ()
	    > param_analyzer_max_recursion_depth)
	  {
	    if (logger)
	      logger->log ("rejecting call edge: recursion limit exceeded");
	    // TODO: issue a sorry for this?
	    return false;
	  }
      }
      break;

    case SUPEREDGE_RETURN:
      {
	/* Require that we return to the call site in the call string.  */
	if (m_call_string->empty_p ())
	  {
	    if (logger)
	      logger->log ("rejecting return edge: empty call string");
	    return false;
	  }
	const call_string::element_t &top_of_stack
	  = m_call_string->get_top_of_stack ();
	m_call_string = m_call_string->get_parent ();
	call_string::element_t current_call_string_element (succ->m_dest,
							    succ->m_src);
	if (top_of_stack != current_call_string_element)
	  {
	    if (logger)
	      logger->log ("rejecting return edge: return to wrong callsite");
	    return false;
	  }
      }
      break;

    case SUPEREDGE_INTRAPROCEDURAL_CALL:
      {
	const callgraph_superedge *cg_sedge
	  = as_a <const callgraph_superedge *> (succ);
	/* Consider turning this edge into a use of an
	   interprocedural summary.  */
	if (eg.get_analysis_plan ().use_summary_p (cg_sedge->m_cedge))
	  {
	    if (logger)
	      logger->log ("using function summary for %qE in %qE",
			   cg_sedge->get_callee_decl (),
			   cg_sedge->get_caller_decl ());
	    return true;
	  }
	else
	  {
	    /* Otherwise, we ignore these edges  */
	    if (logger)
	      logger->log ("rejecting interprocedural edge");
	    return false;
	  }
      }
    }

  return true;
}

/* Comparator for program points within the same supernode,
   for implementing worklist::key_t comparison operators.
   Return negative if POINT_A is before POINT_B
   Return positive if POINT_A is after POINT_B
   Return 0 if they are equal.  */

int
function_point::cmp_within_supernode_1 (const function_point &point_a,
					const function_point &point_b)
{
  gcc_assert (point_a.get_supernode () == point_b.get_supernode ());

  switch (point_a.m_kind)
    {
    default:
      gcc_unreachable ();
    case PK_BEFORE_SUPERNODE:
      switch (point_b.m_kind)
	{
	default:
	  gcc_unreachable ();
	case PK_BEFORE_SUPERNODE:
	  {
	    int a_src_idx = -1;
	    int b_src_idx = -1;
	    if (point_a.m_from_edge)
	      a_src_idx = point_a.m_from_edge->m_src->m_index;
	    if (point_b.m_from_edge)
	      b_src_idx = point_b.m_from_edge->m_src->m_index;
	    return a_src_idx - b_src_idx;
	  }
	  break;

	case PK_BEFORE_STMT:
	case PK_AFTER_SUPERNODE:
	  return -1;
	}
      break;
    case PK_BEFORE_STMT:
      switch (point_b.m_kind)
	{
	default:
	  gcc_unreachable ();
	case PK_BEFORE_SUPERNODE:
	  return 1;

	case PK_BEFORE_STMT:
	  return point_a.m_stmt_idx - point_b.m_stmt_idx;

	case PK_AFTER_SUPERNODE:
	  return -1;
	}
      break;
    case PK_AFTER_SUPERNODE:
      switch (point_b.m_kind)
	{
	default:
	  gcc_unreachable ();
	case PK_BEFORE_SUPERNODE:
	case PK_BEFORE_STMT:
	  return 1;

	case PK_AFTER_SUPERNODE:
	  return 0;
	}
      break;
    }
}

/* Comparator for program points within the same supernode,
   for implementing worklist::key_t comparison operators.
   Return negative if POINT_A is before POINT_B
   Return positive if POINT_A is after POINT_B
   Return 0 if they are equal.  */

int
function_point::cmp_within_supernode (const function_point &point_a,
				      const function_point &point_b)
{
  int result = cmp_within_supernode_1 (point_a, point_b);

  /* Check that the ordering is symmetric  */
#if CHECKING_P
  int reversed = cmp_within_supernode_1 (point_b, point_a);
  gcc_assert (reversed == -result);
#endif

  return result;
}

/* Comparator for imposing an order on function_points.  */

int
function_point::cmp (const function_point &point_a,
		     const function_point &point_b)
{
  int idx_a = point_a.m_supernode ? point_a.m_supernode->m_index : -1;
  int idx_b = point_b.m_supernode ? point_b.m_supernode->m_index : -1;
  if (int cmp_idx = idx_a - idx_b)
    return cmp_idx;
  gcc_assert (point_a.m_supernode == point_b.m_supernode);
  if (point_a.m_supernode)
    return cmp_within_supernode (point_a, point_b);
  else
    return 0;
}

/* Comparator for use by vec<function_point>::qsort.  */

int
function_point::cmp_ptr (const void *p1, const void *p2)
{
  const function_point *fp1 = (const function_point *)p1;
  const function_point *fp2 = (const function_point *)p2;
  return cmp (*fp1, *fp2);
}

/* For PK_BEFORE_STMT, go to next stmt (or to PK_AFTER_SUPERNODE).  */

void
function_point::next_stmt ()
{
  gcc_assert (m_kind == PK_BEFORE_STMT);
  if (++m_stmt_idx == m_supernode->m_stmts.length ())
    {
      m_kind = PK_AFTER_SUPERNODE;
      m_stmt_idx = 0;
    }
}

/* For those function points for which there is a uniquely-defined
   successor, return it.  */

function_point
function_point::get_next () const
{
  switch (get_kind ())
    {
    default:
      gcc_unreachable ();
    case PK_ORIGIN:
    case PK_AFTER_SUPERNODE:
      gcc_unreachable (); /* Not uniquely defined.  */
    case PK_BEFORE_SUPERNODE:
      if (get_supernode ()->m_stmts.length () > 0)
	return before_stmt (get_supernode (), 0);
      else
	return after_supernode (get_supernode ());
    case PK_BEFORE_STMT:
      {
	unsigned next_idx = get_stmt_idx () + 1;
	if (next_idx < get_supernode ()->m_stmts.length ())
	  return before_stmt (get_supernode (), next_idx);
	else
	  return after_supernode (get_supernode ());
      }
    }
}

/* class program_point.  */

program_point
program_point::origin (const region_model_manager &mgr)
{
  return program_point (function_point (NULL, NULL,
					0, PK_ORIGIN),
			mgr.get_empty_call_string ());
}

program_point
program_point::from_function_entry (const region_model_manager &mgr,
				    const supergraph &sg,
				    function *fun)
{
  return program_point (function_point::from_function_entry (sg, fun),
			mgr.get_empty_call_string ());
}

/* For those program points for which there is a uniquely-defined
   successor, return it.  */

program_point
program_point::get_next () const
{
  switch (m_function_point.get_kind ())
    {
    default:
      gcc_unreachable ();
    case PK_ORIGIN:
    case PK_AFTER_SUPERNODE:
      gcc_unreachable (); /* Not uniquely defined.  */
    case PK_BEFORE_SUPERNODE:
      if (get_supernode ()->m_stmts.length () > 0)
	return before_stmt (get_supernode (), 0, get_call_string ());
      else
	return after_supernode (get_supernode (), get_call_string ());
    case PK_BEFORE_STMT:
      {
	unsigned next_idx = get_stmt_idx () + 1;
	if (next_idx < get_supernode ()->m_stmts.length ())
	  return before_stmt (get_supernode (), next_idx, get_call_string ());
	else
	  return after_supernode (get_supernode (), get_call_string ());
      }
    }
}

#if CHECKING_P

namespace selftest {

/* Verify that function_point::operator== works as expected.  */

static void
test_function_point_equality ()
{
  const supernode *snode = NULL;

  function_point a = function_point (snode, NULL, 0,
				     PK_BEFORE_SUPERNODE);
  function_point b = function_point::before_supernode (snode, NULL);
  ASSERT_EQ (a, b);
}

/* Verify that function_point::cmp_within_supernode works as expected.  */

static void
test_function_point_ordering ()
{
  const supernode *snode = NULL;

  /* Populate an array with various points within the same
     snode, in order.  */
  auto_vec<function_point> points;
  points.safe_push (function_point::before_supernode (snode, NULL));
  points.safe_push (function_point::before_stmt (snode, 0));
  points.safe_push (function_point::before_stmt (snode, 1));
  points.safe_push (function_point::after_supernode (snode));

  /* Check all pairs.  */
  unsigned i;
  function_point *point_a;
  FOR_EACH_VEC_ELT (points, i, point_a)
    {
      unsigned j;
      function_point *point_b;
      FOR_EACH_VEC_ELT (points, j, point_b)
	{
	  int cmp = function_point::cmp_within_supernode (*point_a, *point_b);
	  if (i == j)
	    ASSERT_EQ (cmp, 0);
	  if (i < j)
	    ASSERT_TRUE (cmp < 0);
	  if (i > j)
	    ASSERT_TRUE (cmp > 0);
	}
    }
}

/* Verify that program_point::operator== works as expected.  */

static void
test_program_point_equality ()
{
  region_model_manager mgr;

  const supernode *snode = NULL;

  const call_string &cs = mgr.get_empty_call_string ();

  program_point a = program_point::before_supernode (snode, NULL,
						     cs);

  program_point b = program_point::before_supernode (snode, NULL,
						     cs);

  ASSERT_EQ (a, b);
  // TODO: verify with non-empty callstrings, with different edges
}

/* Run all of the selftests within this file.  */

void
analyzer_program_point_cc_tests ()
{
  test_function_point_equality ();
  test_function_point_ordering ();
  test_program_point_equality ();
}

} // namespace selftest

#endif /* CHECKING_P */

} // namespace ana

#endif /* #if ENABLE_ANALYZER */