graphs.h

/*
 * SPDX-FileCopyrightText: 2013 Barefoot Networks, Inc.
 * Copyright 2013-present Barefoot Networks, Inc.
 *
 * SPDX-License-Identifier: Apache-2.0
 */
 
#ifndef BACKENDS_GRAPHS_GRAPHS_H_
#define BACKENDS_GRAPHS_GRAPHS_H_
 
#include "config.h"
#include "lib/cstring.h"

#ifndef HAVE_LIBBOOST_GRAPH
#error "This backend requires the boost graph headers, which could not be found"
#endif
 
#include <map>
#include <optional>
#include <utility>  // std::pair
#include <vector>
 
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/graphviz.hpp>
 
#include "frontends/p4/parserCallGraph.h"
#include "ir/ir.h"
#include "ir/visitor.h"
 
namespace P4 {
 
class ReferenceMap;
class TypeMap;
 
}  // namespace P4
 
namespace P4::graphs {
 
using namespace P4::literals;
 
class EdgeTypeIface {
 public:
    virtual ~EdgeTypeIface() {}
    virtual cstring label() const = 0;
};
 
class EdgeUnconditional : public EdgeTypeIface {
 public:
    EdgeUnconditional() = default;
    cstring label() const override { return cstring::empty; };
};
 
class EdgeIf : public EdgeTypeIface {
 public:
    enum class Branch { TRUE, FALSE };
    explicit EdgeIf(Branch branch) : branch(branch) {}
    cstring label() const override {
        switch (branch) {
            case Branch::TRUE:
                return "TRUE"_cs;
            case Branch::FALSE:
                return "FALSE"_cs;
        }
        BUG("unreachable");
        return cstring::empty;
    };
 
 private:
    Branch branch;
};
 
class EdgeSwitch : public EdgeTypeIface {
 public:
    explicit EdgeSwitch(const IR::Expression *labelExpr) : labelExpr(labelExpr) {}
    cstring label() const override {
        std::stringstream sstream;
        labelExpr->dbprint(sstream);
        return cstring(sstream);
    };
 
 private:
    const IR::Expression *labelExpr;
};
 
class Graphs : public Inspector {
 public:
    enum class VertexType {
        TABLE,
        KEY,
        ACTION,
        CONDITION,
        SWITCH,
        STATEMENTS,
        CONTROL,
        OTHER,
        STATE,
        EMPTY
    };
    struct Vertex {
        cstring name;
        VertexType type;
    };

    using GraphvizAttributes = std::map<cstring, cstring>;
    using vertexProperties = boost::property<boost::vertex_attribute_t, GraphvizAttributes, Vertex>;
    using edgeProperties = boost::property<
        boost::edge_attribute_t, GraphvizAttributes,
        boost::property<boost::edge_name_t, cstring, boost::property<boost::edge_index_t, int>>>;
    using graphProperties = boost::property<
        boost::graph_name_t, std::string,
        boost::property<
            boost::graph_graph_attribute_t, GraphvizAttributes,
            boost::property<boost::graph_vertex_attribute_t, GraphvizAttributes,
                            boost::property<boost::graph_edge_attribute_t, GraphvizAttributes>>>>;
    using Graph_ = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
                                         vertexProperties, edgeProperties, graphProperties>;
    using Graph = boost::subgraph<Graph_>;
    using vertex_t = boost::graph_traits<Graph>::vertex_descriptor;
 
    using Parents = std::vector<std::pair<vertex_t, EdgeTypeIface *>>;

    std::optional<vertex_t> merge_other_statements_into_vertex();
 
    vertex_t add_vertex(const cstring &name, VertexType type);
    vertex_t add_and_connect_vertex(const cstring &name, VertexType type);
    void add_edge(const vertex_t &from, const vertex_t &to, const cstring &name);
    void add_edge(const vertex_t &from, const vertex_t &to, const cstring &name,
                  unsigned cluster_id);
 
    class GraphAttributeSetter {
     public:
        void operator()(Graph &g) const {
            auto vertices = boost::vertices(g);
            for (auto &vit = vertices.first; vit != vertices.second; ++vit) {
                const auto &vinfo = g[*vit];
                auto attrs = boost::get(boost::vertex_attribute, g);
                attrs[*vit]["label"_cs] = vinfo.name;
                attrs[*vit]["style"_cs] = vertexTypeGetStyle(vinfo.type);
                attrs[*vit]["shape"_cs] = vertexTypeGetShape(vinfo.type);
                attrs[*vit]["margin"_cs] = vertexTypeGetMargin(vinfo.type);
            }
            auto edges = boost::edges(g);
            for (auto &eit = edges.first; eit != edges.second; ++eit) {
                auto attrs = boost::get(boost::edge_attribute, g);
                attrs[*eit]["label"_cs] = boost::get(boost::edge_name, g, *eit);
            }
        }
 
     private:
        static cstring vertexTypeGetShape(VertexType type) {
            switch (type) {
                case VertexType::TABLE:
                case VertexType::ACTION:
                    return "ellipse"_cs;
                default:
                    return "rectangle"_cs;
            }
            BUG("unreachable");
            return cstring::empty;
        }
 
        static cstring vertexTypeGetStyle(VertexType type) {
            switch (type) {
                case VertexType::CONTROL:
                    return "dashed"_cs;
                case VertexType::EMPTY:
                    return "invis"_cs;
                case VertexType::KEY:
                case VertexType::CONDITION:
                case VertexType::SWITCH:
                    return "rounded"_cs;
                default:
                    return "solid"_cs;
            }
            BUG("unreachable");
            return cstring::empty;
        }
 
        static cstring vertexTypeGetMargin(VertexType type) {
            switch (type) {
                default:
                    return cstring::empty;
            }
        }
    };  // end class GraphAttributeSetter
 
 protected:
    Graph *g{nullptr};
    vertex_t start_v{};
    vertex_t exit_v{};
    Parents parents{};
    std::vector<const IR::Statement *> statementsStack{};
 
 private:
    void limitStringSize(std::stringstream &sstream, std::stringstream &helper_sstream);
};
 
}  // namespace P4::graphs
 
#endif /* BACKENDS_GRAPHS_GRAPHS_H_ */