call_graph.h

Go to the documentation of this file.

/*******************************************************************\
 
Module: Function Call Graphs
 
Author: Daniel Kroening, kroening@kroening.com
 
\*******************************************************************/
 
 
#ifndef CPROVER_ANALYSES_CALL_GRAPH_H
#define CPROVER_ANALYSES_CALL_GRAPH_H
 
#include <iosfwd>
#include <map>
#include <unordered_set>
 
#include <util/graph.h>
 
#include <goto-programs/goto_program.h>
 
class goto_functionst;
class goto_modelt;
 
class call_grapht
{
public:
  explicit call_grapht(bool collect_callsites=false);
  explicit call_grapht(const goto_modelt &, bool collect_callsites=false);
  explicit call_grapht(const goto_functionst &, bool collect_callsites=false);
 
  // These two functions build a call graph restricted to functions
  // reachable from the given root.
 
  static call_grapht create_from_root_function(
    const goto_modelt &model,
    const irep_idt &root,
    bool collect_callsites)
  {
    return call_grapht(model, root, collect_callsites);
  }
 
  static call_grapht create_from_root_function(
    const goto_functionst &functions,
    const irep_idt &root,
    bool collect_callsites)
  {
    return call_grapht(functions, root, collect_callsites);
  }
 
  // Constructors used to implement the above:
 
private:
  call_grapht(
    const goto_modelt &model,
    const irep_idt &root,
    bool collect_callsites);
  call_grapht(
    const goto_functionst &functions,
    const irep_idt &root,
    bool collect_callsites);
 
public:
 
  void output_dot(std::ostream &out) const;
  void output(std::ostream &out) const;
  void output_xml(std::ostream &out) const;
 
  typedef std::unordered_set<irep_idt, irep_id_hash> nodest;
 
  typedef std::multimap<irep_idt, irep_idt> edgest;
 
  typedef std::pair<irep_idt, irep_idt> edget;
 
  typedef goto_programt::const_targett locationt;
 
  typedef std::set<locationt> locationst;
 
  typedef std::map<edget, locationst> callsitest;
 
  edgest edges;
  nodest nodes;
 
  callsitest callsites;
 
  void add(const irep_idt &caller, const irep_idt &callee);
  void add(const irep_idt &caller, const irep_idt &callee, locationt callsite);
 
  call_grapht get_inverted() const;
 
  struct edge_with_callsitest
  {
    locationst callsites;
  };
 
  struct function_nodet : public graph_nodet<edge_with_callsitest>
  {
    irep_idt function;
  };
 
  class directed_grapht : public ::grapht<function_nodet>
  {
    friend class call_grapht;
 
    std::unordered_map<irep_idt, node_indext> nodes_by_name;
 
  public:
    optionalt<node_indext> get_node_index(const irep_idt &function) const;
 
    typedef std::unordered_map<irep_idt, node_indext> nodes_by_namet;
 
    const nodes_by_namet &get_nodes_by_name() const
    {
      return nodes_by_name;
    }
  };
 
  directed_grapht get_directed_graph() const;
 
protected:
  void add(const irep_idt &function,
           const goto_programt &body);
private:
  bool collect_callsites;
  std::string format_callsites(const edget &edge) const;
};
 
#endif // CPROVER_ANALYSES_CALL_GRAPH_H