GraphViz.h

#ifndef ROSE_BinaryAnalysis_Partitioner2_GraphViz_H
#define ROSE_BinaryAnalysis_Partitioner2_GraphViz_H
#include <featureTests.h>
#ifdef ROSE_ENABLE_BINARY_ANALYSIS

#include <ostream>
#include <Rose/BinaryAnalysis/NoOperation.h>
#include <Rose/BinaryAnalysis/SourceLocations.h>
#include <boost/regex.hpp>
#include <Rose/Color.h>
#include <Rose/BinaryAnalysis/Partitioner2/ControlFlowGraph.h>
#include <Rose/BinaryAnalysis/Partitioner2/FunctionCallGraph.h>

namespace Rose {
namespace BinaryAnalysis {
namespace Partitioner2 {

namespace GraphViz {

typedef Sawyer::Container::Map<std::string, std::string> Attributes;

ROSE_DLL_API std::string toString(const Attributes&);

ROSE_DLL_API std::string quotedEscape(const std::string&);

ROSE_DLL_API std::string htmlEscape(const std::string&);

ROSE_DLL_API std::string escape(const std::string&);

ROSE_DLL_API std::string concatenate(const std::string &oldStuff, const std::string &newStuff, const std::string &separator="");

ROSE_DLL_API bool isId(const std::string &s);

ROSE_DLL_API extern const size_t NO_ID;


class ROSE_DLL_API Organization {
private:
    bool isSelected_;
    std::string name_;                                  // name used by GraphViz to identify this object
    std::string label_;                                 // label shown in rendered graph, includes delimiters, "" or <>
    Attributes attributes_;
    std::string subgraph_;
public:
    Organization(): isSelected_(true) {}

    void select(bool b=true) { isSelected_ = b; }

    bool isSelected() const { return isSelected_; }

    const std::string &name() const { return name_; }
    void name(const std::string &s) { name_ = s; }
    const std::string& label() const {
        static std::string empty = "\"\"";
        return label_.empty() ? empty : label_;
    }
    void label(const std::string &s) { label_ = s; }
    const Attributes& attributes() const { return attributes_; }
    Attributes& attributes() { return attributes_; }
    void attributes(const Attributes &a) { attributes_ = a; }
    const std::string& subgraph() const { return subgraph_; }
    void subgraph(const std::string &s) { subgraph_ = s; }
};

//                                      BaseEmitter

template<class G>
class BaseEmitter {
public:
    typedef G Graph;

    typedef std::vector<Organization> VertexOrganization;

    typedef std::vector<Organization> EdgeOrganization;

    typedef Sawyer::Container::Map<std::string, Organization> SubgraphOrganization;

protected:
    struct PseudoEdge {
        typename G::ConstVertexIterator src, dst;
        std::string label;
        Attributes attributes;
        PseudoEdge(const typename G::ConstVertexIterator &src, const typename G::ConstVertexIterator &dst,
                   const std::string &label)
            : src(src), dst(dst), label(label) {}
    };

    typedef Sawyer::Container::Map<size_t, size_t> VMap;// maps graph vertex ID to graphviz node ID

protected:
    Graph graph_;                                       // graph being emitted
    VertexOrganization vertexOrganization_;             // which vertices are selected for output
    EdgeOrganization edgeOrganization_;                 // which edges are selected for output
    SubgraphOrganization subgraphOrganization_;         // which subgraphs are selected for output
    Attributes defaultGraphAttributes_;                 // default attributes for the graph as a whole
    Attributes defaultNodeAttributes_;                  // default attributes for graph nodes (CFG vertices and other)
    Attributes defaultEdgeAttributes_;                  // default attributes for graph edges
    std::list<PseudoEdge> pseudoEdges_;                 // extra edges not present in the CFG but needed in the GraphViz
    Color::HSV subgraphColor_;                          // background color for function subgraphs

public:
    BaseEmitter(): subgraphColor_(0, 0, 0.95) {}
    
    explicit BaseEmitter(const Graph &g)
        : subgraphColor_(0, 0, 0.95) {
        graph(g);
    }

    void graph(const Graph &g) {
        graph_ = g;
        vertexOrganization_.clear();
        vertexOrganization_.resize(g.nVertices());
        edgeOrganization_.clear();
        edgeOrganization_.resize(g.nEdges());
        subgraphOrganization_.clear();
        pseudoEdges_.clear();
    }

    Attributes& defaultGraphAttributes() {
        return defaultGraphAttributes_;
    }
    const Attributes& defaultGraphAttributes() const {
        return defaultGraphAttributes_;
    }
    Attributes& defaultNodeAttributes() {
        return defaultNodeAttributes_;
    }
    const Attributes& defaultNodeAttributes() const {
        return defaultNodeAttributes_;
    }
    Attributes& defaultEdgeAttributes() {
        return defaultEdgeAttributes_;
    }
    const Attributes& defaultEdgeAttributes() const {
        return defaultEdgeAttributes_;
    }
    const Color::HSV& subgraphColor() const { return subgraphColor_; }
    void subgraphColor(const Color::HSV &bg) { subgraphColor_ = bg; }
    const VertexOrganization& vertexOrganization() const {
        return vertexOrganization_;
    }
    VertexOrganization& vertexOrganization() {
        return vertexOrganization_;
    }
    const Organization& vertexOrganization(size_t vertexId) const {
        ASSERT_require(vertexId < vertexOrganization_.size());
        return vertexOrganization_[vertexId];
    }
    Organization& vertexOrganization(size_t vertexId) {
        ASSERT_require(vertexId < vertexOrganization_.size());
        return vertexOrganization_[vertexId];
    }
    const Organization& vertexOrganization(const typename G::ConstVertexIterator &vertex) const {
        return vertexOrganization(vertex->id());
    }
    const Organization& vertexOrganization(const typename G::Vertex &vertex) const {
        return vertexOrganization(vertex.id());
    }
    Organization& vertexOrganization(const typename G::ConstVertexIterator &vertex) {
        return vertexOrganization(vertex->id());
    }
    Organization& vertexOrganization(const typename G::Vertex &vertex) {
        return vertexOrganization(vertex.id());
    }
    const EdgeOrganization& edgeOrganization() const {
        return edgeOrganization_;
    }
    EdgeOrganization& edgeOrganization() {
        return edgeOrganization_;
    }
    const Organization& edgeOrganization(size_t edgeId) const {
        ASSERT_require(edgeId < edgeOrganization_.size());
        return edgeOrganization_[edgeId];
    }
    Organization& edgeOrganization(size_t edgeId) {
        ASSERT_require(edgeId < edgeOrganization_.size());
        return edgeOrganization_[edgeId];
    }
    const Organization& edgeOrganization(const typename G::ConstEdgeIterator &edge) const {
        return edgeOrganization(edge->id());
    }
    const Organization& edgeOrganization(const typename G::Edge &edge) const {
        return edgeOrganization(edge.id());
    }
    Organization& edgeOrganization(const typename G::ConstEdgeIterator &edge) {
        return edgeOrganization(edge->id());
    }
    Organization& edgeOrganization(const typename G::Edge &edge) {
        return edgeOrganization(edge.id());
    }
    const SubgraphOrganization& subgraphOrganization() const {
        return subgraphOrganization_;
    }
    SubgraphOrganization& subgraphOrganization() {
        return subgraphOrganization_;
    }
    const Organization& subgraphOrganization(const std::string &name) const {
        return subgraphOrganization_.getOrDefault(name);
    }
    Organization& subgraphOrganization(const std::string &name) {
        return subgraphOrganization_.insertMaybeDefault(name);
    }
    void selectAll(bool b=true) {
        selectAllVertices(b);
        selectAllEdges(b);
    }

    void selectNone() {
        pseudoEdges_.clear();
        selectAllEdges(false);
        selectAllVertices(false);
    }

    void selectAllVertices(bool b=true) {
        BOOST_FOREACH (Organization &org, vertexOrganization_)
            org.select(b);
    }

    void selectAllEdges(bool b=true) {
        BOOST_FOREACH (Organization &org, edgeOrganization_)
            org.select(b);
    }

    void deselectParallelEdges();
    
    virtual void emit(std::ostream&) const;

protected:
    size_t emitVertex(std::ostream&, const typename G::ConstVertexIterator&, const Organization&, const VMap&) const;

    void emitEdge(std::ostream&, const typename G::ConstEdgeIterator&, const Organization&, const VMap&) const;

};


//                              Base generator for Partitioner2::ControlFlowGraph

class ROSE_DLL_API CfgEmitter: public BaseEmitter<ControlFlowGraph> {
    const Partitioner &partitioner_;
    bool useFunctionSubgraphs_;                         // should called functions be shown as subgraphs?
    bool showReturnEdges_;                              // show E_FUNCTION_RETURN edges?
    bool showInstructions_;                             // show instructions or only block address?
    bool showInstructionAddresses_;                     // if instructions are shown, show addresses too?
    bool showInstructionStackDeltas_;                   // show stack deltas for instructions
    bool showInNeighbors_;                              // show neighbors for incoming edges to selected vertices?
    bool showOutNeighbors_;                             // show neighbors for outgoing edges to selected vertices?
    bool strikeNoopSequences_;                          // render no-op sequences in a different style
    Color::HSV funcEnterColor_;                         // background color for function entrance blocks
    Color::HSV funcReturnColor_;                        // background color for function return blocks
    Color::HSV warningColor_;                           // background color for special nodes and warnings
    SourceLocations srcMapper_;                         // maps addresses to source code (optional)
    static unsigned long versionDate_;                  // date code from "dot -V", like 20100126
    NoOperation noOpAnalysis_;

public:
    explicit CfgEmitter(const Partitioner&);
    CfgEmitter(const Partitioner&, const ControlFlowGraph&);
    // Properties

    const Partitioner& partitioner() { return partitioner_; }

    bool useFunctionSubgraphs() const { return useFunctionSubgraphs_; }
    void useFunctionSubgraphs(bool b) { useFunctionSubgraphs_ = b; }
    bool showInstructions() const { return showInstructions_; }
    void showInstructions(bool b) { showInstructions_ = b; }
    bool showInstructionAddresses() const { return showInstructionAddresses_; }
    void showInstructionAddresses(bool b) { showInstructionAddresses_ = b; }
    bool showInstructionStackDeltas() const { return showInstructionStackDeltas_; }
    void showInstructionStackDeltas(bool b) { showInstructionStackDeltas_ = b; }
    bool strikeNoopSequences() const { return strikeNoopSequences_; }
    void strikeNoopSequences(bool b) { strikeNoopSequences_ = b; }
    const Color::HSV& funcEnterColor() const { return funcEnterColor_; }
    void funcEnterColor(const Color::HSV &bg) { funcEnterColor_ = bg; }
    const Color::HSV& funcReturnColor() const { return funcReturnColor_; }
    void funcReturnColor(const Color::HSV &bg) { funcReturnColor_ = bg; }
    const Color::HSV& warningColor() const { return warningColor_; }
    void warningColor(const Color::HSV &bg) { warningColor_ = bg; }
    bool showOutNeighbors() const { return showOutNeighbors_; }
    void showOutNeighbors(bool b) { showOutNeighbors_ = b; }
    bool showInNeighbors() const { return showInNeighbors_; }
    void showInNeighbors(bool b) { showInNeighbors_ = b; }
    bool showReturnEdges() const { return showReturnEdges_; }
    void showReturnEdges(bool b) { showReturnEdges_ = b; }
    const SourceLocations& srcMapper() const { return srcMapper_; }
    SourceLocations& srcMapper() { return srcMapper_; }
    void srcMapper(const SourceLocations &mapper) { srcMapper_ = mapper; }
    // Organization

    // Low-level vertex and edge selection

    void selectInterval(const AddressInterval&);

    void selectIntraFunction(const Function::Ptr&);

    void selectFunctionCallees(const Function::Ptr&);

    void selectFunctionCallers(const Function::Ptr&);

    void deselectReturnEdges();

    void deselectUnusedVertex(ControlFlowGraph::ConstVertexIterator);

    void deselectUnusedVertexType(VertexType);

    void selectNeighbors(bool selectInEdges=true, bool selectOutEdges=true);

    // High-level selectors

    CfgEmitter& selectWholeGraph();

    CfgEmitter& selectFunctionGraph(const Function::Ptr&);

    CfgEmitter& selectIntervalGraph(const AddressInterval &interval);

    // GraphViz emitters
    
    void emitWholeGraph(std::ostream &out) {
        selectWholeGraph().emit(out);
    }

    void emitFunctionGraph(std::ostream &out, const Function::Ptr &function) {
        selectFunctionGraph(function).emit(out);
    }

    void emitIntervalGraph(std::ostream &out, const AddressInterval &interval) {
        selectIntervalGraph(interval).emit(out);
    }
    

    // Low-level emitters

    // Utilities

    static bool isInterFunctionEdge(const ControlFlowGraph::Edge&);
    static bool isInterFunctionEdge(const ControlFlowGraph::ConstEdgeIterator &e) { return isInterFunctionEdge(*e); }
    static Function::Ptr firstOwningFunction(const ControlFlowGraph::Vertex&);
    static Function::Ptr firstOwningFunction(const ControlFlowGraph::ConstVertexIterator &v) {
        return firstOwningFunction(*v);
    }
    static FunctionSet owningFunctions(const ControlFlowGraph::Vertex&);
    static FunctionSet owningFunctions(const ControlFlowGraph::ConstVertexIterator &v) { return owningFunctions(*v); }
    void assignFunctionSubgraphs();


    // Formatting: these are expected to be overridden by subclasses

    virtual std::string sourceLocation(const ControlFlowGraph::ConstVertexIterator&) const;

    virtual std::string vertexLabel(const ControlFlowGraph::ConstVertexIterator&) const;
    std::string vertexLabel(const ControlFlowGraph::Vertex&) const;
    virtual std::string vertexLabelDetailed(const ControlFlowGraph::ConstVertexIterator&) const;
    std::string vertexLabelDetailed(const ControlFlowGraph::Vertex&) const;
    virtual Attributes vertexAttributes(const ControlFlowGraph::ConstVertexIterator&) const;
    Attributes vertexAttributes(const ControlFlowGraph::Vertex&) const;
    virtual std::string edgeLabel(const ControlFlowGraph::ConstEdgeIterator&) const;
    std::string edgeLabel(const ControlFlowGraph::Edge&) const;
    virtual Attributes edgeAttributes(const ControlFlowGraph::ConstEdgeIterator&) const;
    Attributes edgeAttributes(const ControlFlowGraph::Edge&) const;
    virtual std::string functionLabel(const Function::Ptr&) const;

    virtual Attributes functionAttributes(const Function::Ptr&) const;

private:
    void init();

    // Give GraphViz identifying names to some vertices. The names assigned by this method are used internally by GraphViz, but
    // encoding some information into thse names (instead of using integers) is useful mainly if we try to parse the GraphViz
    // output later --  it gives us a way to relate GraphViz's vertex identifiers back to the original ROSE CFG vertices.
    void nameVertices();
};


//                              Base emitter for Partitioner2::FunctionCallGraph

class ROSE_DLL_API CgEmitter: public BaseEmitter<FunctionCallGraph::Graph> {
    FunctionCallGraph cg_;
    Color::HSV functionHighlightColor_;                 // highlight certain functions
    boost::regex highlightNameMatcher_;                 // which functions to highlight
public:
    explicit CgEmitter(const Partitioner &partitioner);
    CgEmitter(const Partitioner &partitioner, const FunctionCallGraph &cg);
    virtual std::string functionLabel(const Function::Ptr&) const;
    virtual Attributes functionAttributes(const Function::Ptr&) const;
    virtual void emitCallGraph(std::ostream &out) const;
    virtual const FunctionCallGraph& callGraph() const { return cg_; }
    virtual void callGraph(const FunctionCallGraph &cg);
    virtual void highlight(const boost::regex&);
private:
    // Give GraphViz identifying names to some vertices. The names assigned by this method are used internally by GraphViz, but
    // encoding some information into thse names (instead of using integers) is useful mainly if we try to parse the GraphViz
    // output later --  it gives us a way to relate GraphViz's vertex identifiers back to the original ROSE CFG vertices.
    void nameVertices();
};


//                              Callgraph emitter with inlined imports

class ROSE_DLL_API CgInlinedEmitter: public CgEmitter {
    boost::regex nameMatcher_;
    typedef std::vector<Function::Ptr> InlinedFunctions;
    typedef Sawyer::Container::Map<Function::Ptr, InlinedFunctions> Inlines;
    Inlines inlines_;
public:
    CgInlinedEmitter(const Partitioner &partitioner, const boost::regex &nameMatcher);
    CgInlinedEmitter(const Partitioner &partitioner, const FunctionCallGraph &cg, const boost::regex &nameMatcher);
    virtual const FunctionCallGraph& callGraph() const ROSE_OVERRIDE { return CgEmitter::callGraph(); }
    virtual void callGraph(const FunctionCallGraph&) ROSE_OVERRIDE;
    virtual std::string functionLabel(const Function::Ptr&) const ROSE_OVERRIDE;
    virtual bool shouldInline(const Function::Ptr&) const;
};


//                                      Reading layout position information from "dot"

struct Coordinate {
    double x;                                           
    double y;                                           
};

struct VertexPosition {
    std::string name;                                   
    Coordinate center;                                  
    double width;                                       
    double height;                                      
};

struct EdgePosition {
    std::vector<Coordinate> spline;                     
};

typedef Sawyer::Container::Graph<VertexPosition, EdgePosition> PositionGraph;

PositionGraph readPositions(std::istream&);


    

//                                      Class template method implementations

template<class G>
size_t
BaseEmitter<G>::emitVertex(std::ostream &out, const typename G::ConstVertexIterator &vertex,
                           const Organization &org, const VMap &vmap) const {
    size_t id = NO_ID;
    if (org.isSelected() && !vmap.getOptional(vertex->id()).assignTo(id)) {
        id = vmap.size();
        std::string name = org.name();
        if (name.empty())
            name = StringUtility::numberToString(id);
        out <<name <<" [ label=" <<org.label() <<" ";
        out <<toString(org.attributes()) <<" ];\n";
    }
    return id;
}

template<class G>
void
BaseEmitter<G>::emitEdge(std::ostream &out, const typename G::ConstEdgeIterator &edge, const Organization &org,
                         const VMap &vmap) const {
    ASSERT_require2(vmap.exists(edge->source()->id()), "edge source vertex has not yet been emitted");
    ASSERT_require2(vmap.exists(edge->target()->id()), "edge target vertex has not yet been emitted");

    size_t sourceId = edge->source()->id();
    std::string sourceName = vertexOrganization(sourceId).name();
    if (sourceName.empty())
        sourceName = StringUtility::numberToString(vmap[sourceId]);

    size_t targetId = edge->target()->id();
    std::string targetName = vertexOrganization(targetId).name();
    if (targetName.empty())
        targetName = StringUtility::numberToString(vmap[targetId]);

    out <<sourceName <<" -> " <<targetName <<" [ label=" <<org.label() <<" " <<toString(org.attributes()) <<" ];\n";
}

template<class G>
void
BaseEmitter<G>::emit(std::ostream &out) const {
    VMap vmap;                                          // GraphViz node ID for each graph vertex (modified by emit)

    out <<"digraph CFG {\n";
    out <<" graph [ " <<toString(defaultGraphAttributes_) <<" ];\n";
    out <<" node  [ " <<toString(defaultNodeAttributes_) <<" ];\n";
    out <<" edge  [ " <<toString(defaultEdgeAttributes_) <<" ];\n";

    typedef std::map<std::string /*subgraph name*/, std::string/*subgraph content*/> Subgraphs;
    Subgraphs subgraphs;

    // Emit vertices to subgraphs
    for (typename G::ConstVertexIterator vertex=graph_.vertices().begin(); vertex!=graph_.vertices().end(); ++vertex) {
        const Organization &org = vertexOrganization(vertex);
        if (org.isSelected() && !vmap.exists(vertex->id())) {
            std::ostringstream ss;
            size_t gvid = emitVertex(ss, vertex, org, vmap);
            vmap.insert(vertex->id(), gvid);
            subgraphs[org.subgraph()] += ss.str();
        }
    }

    // Emit edges to subgraphs
    for (typename G::ConstEdgeIterator edge=graph_.edges().begin(); edge!=graph_.edges().end(); ++edge) {
        const Organization &org = edgeOrganization(edge);
        if (org.isSelected() &&
            vertexOrganization(edge->source()).isSelected() && vertexOrganization(edge->target()).isSelected()) {
            std::ostringstream ss;
            emitEdge(ss, edge, org, vmap);
            subgraphs[org.subgraph()] += ss.str();
        }
    }

    // Emit named subgraphs to output
    BOOST_FOREACH (const Subgraphs::value_type &node, subgraphs) {
        const std::string &subgraphName = node.first;
        const std::string &subgraphContent = node.second;
        if (!subgraphName.empty()) {
            out <<"\nsubgraph cluster_" <<subgraphName <<" {"
                <<" label=" <<subgraphOrganization(subgraphName).label() <<" "
                <<toString(subgraphOrganization(subgraphName).attributes()) <<"\n"
                <<subgraphContent
                <<"}\n";
        }
    }

    // Emit unnamed subgraph content without a surrounding subgraph construct (i.e., global graph)
    Subgraphs::iterator unnamedSubgraph = subgraphs.find("");
    if (unnamedSubgraph != subgraphs.end())
        out <<unnamedSubgraph->second;

    // Emit pseudo edges
    BOOST_FOREACH (const PseudoEdge &edge, pseudoEdges_) {
        if (vertexOrganization(edge.src).isSelected() && vertexOrganization(edge.dst).isSelected()) {
            std::string sourceName = vertexOrganization(edge.src).name();
            std::string targetName = vertexOrganization(edge.dst).name();
            out <<(sourceName.empty() ? StringUtility::numberToString(vmap[edge.src->id()]) : sourceName)
                <<" -> "
                <<(targetName.empty() ? StringUtility::numberToString(vmap[edge.dst->id()]) : targetName)
                <<" [ label=" <<escape(edge.label) <<" ];\n";
        }
    }
    
    out <<"}\n";
}

template<class G>
void
BaseEmitter<G>::deselectParallelEdges() {
    BOOST_FOREACH (const typename G::Vertex &src, graph_.vertices()) {
        if (vertexOrganization(src).isSelected()) {
            std::set<size_t> targets;
            BOOST_FOREACH (const typename G::Edge &edge, src.outEdges()) {
                if (edgeOrganization(edge).isSelected() && !targets.insert(edge.target()->id()).second)
                    edgeOrganization(edge).select(false);
            }
        }
    }
}

} // namespace
} // namespace
} // namespace
} // namespace

#endif
#endif