reachability.h

#ifndef COMMON_COMPILER_REACHABILITY_H_
#define COMMON_COMPILER_REACHABILITY_H_
 
#include <list>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
 
#include "frontends/p4/callGraph.h"
#include "ir/id.h"
#include "ir/ir.h"
#include "ir/node.h"
#include "ir/visitor.h"
#include "lib/cstring.h"
#include "lib/null.h"
 
namespace P4Tools {
 
using DCGVertexType = const IR::Node;
using DCGVertexTypeSet = std::unordered_set<const DCGVertexType *>;
using ReachabilityHashType = std::unordered_map<cstring, std::unordered_set<const DCGVertexType *>>;
 
template <class T>
class ExtendedCallGraph : public P4::CallGraph<T> {
    friend class P4ProgramDCGCreator;
    ReachabilityHashType hash;
 
 public:
    explicit ExtendedCallGraph(std::string_view name) : P4::CallGraph<T>(name) {}
    const ReachabilityHashType &getHash() const { return hash; }
    void addToHash(T vertex, IR::ID name) {
        if (name.name.size() == 0) {
            return;
        }
        auto i = hash.find(name.name);
        if (i == hash.end()) {
            std::unordered_set<const DCGVertexType *> s;
            s.insert(vertex);
            hash.emplace(name.name, s);
        } else {
            i->second.insert(vertex);
        }
        const auto *prev = name.name.findlast('.');
        if (prev != nullptr) {
            cstring newName = name.name.before(prev);
            i = hash.find(newName);
            if (i == hash.end()) {
                addToHash(vertex, (newName.size() ? IR::ID(newName) : IR::ID()));
            }
        }
    }
 
    bool isReachable(T start, T element) const {
        CHECK_NULL(start);
        CHECK_NULL(element);
        std::set<T> work;
        std::set<T> visited;
        work.emplace(start);
        while (!work.empty()) {
            auto *node = *work.begin();
            if (node->equiv(*element)) {
                return true;
            }
            work.erase(node);
            if (visited.find(node) != visited.end()) {
                continue;
            }
            visited.emplace(node);
            auto edges = this->out_edges.find(node);
            if (edges == this->out_edges.end()) {
                continue;
            }
            for (auto c : *(edges->second)) {
                work.emplace(c);
            }
        }
        return false;
    }
};
 
using NodesCallGraph = ExtendedCallGraph<DCGVertexType *>;
 
class P4ProgramDCGCreator : public Inspector {
    NodesCallGraph *dcg;
    DCGVertexTypeSet prev;
    std::unordered_set<const DCGVertexType *> visited;
    const IR::P4Program *p4program;
 
 public:
    explicit P4ProgramDCGCreator(NodesCallGraph *dcg);
 
    bool preorder(const IR::Annotation *annotation) override;
    bool preorder(const IR::ConstructorCallExpression *callExpr) override;
    bool preorder(const IR::MethodCallExpression *method) override;
    bool preorder(const IR::MethodCallStatement *method) override;
    bool preorder(const IR::P4Action *action) override;
    bool preorder(const IR::P4Parser *parser) override;
    bool preorder(const IR::P4Table *table) override;
    bool preorder(const IR::ParserState *parserState) override;
    bool preorder(const IR::P4Control *control) override;
    bool preorder(const IR::P4Program *program) override;
    bool preorder(const IR::P4ValueSet *valueSet) override;
    bool preorder(const IR::SelectExpression *selectExpression) override;
    bool preorder(const IR::IfStatement *ifStatement) override;
    bool preorder(const IR::SwitchStatement *switchStatement) override;
    bool preorder(const IR::StatOrDecl *statOrDecl) override;
 
 protected:
    void addEdge(const DCGVertexType *vertex, IR::ID vertexName = IR::ID());
};
 
class ReachabilityEngineState {
    const DCGVertexType *prevNode = nullptr;
    std::list<const DCGVertexType *> state;
 
 public:
    static ReachabilityEngineState *getInitial();
    ReachabilityEngineState *copy();
    std::list<const DCGVertexType *> getState();
    void setState(std::list<const DCGVertexType *>);
    const DCGVertexType *getPrevNode();
    void setPrevNode(const DCGVertexType *);
    bool isEmpty();
    void clear();
};
 
using ReachabilityResult = std::pair<bool, const IR::Expression *>;
 
//                    Engine if corresponded <p4c node name> was reached.
class ReachabilityEngine {
    const NodesCallGraph &dcg;
    const ReachabilityHashType &hash;
    std::unordered_map<const DCGVertexType *, std::list<const DCGVertexType *>> userTransitions;
    std::unordered_map<const DCGVertexType *, const IR::Expression *> conditions;
    std::unordered_set<const DCGVertexType *> forbiddenVertexes;
 
 public:
    ReachabilityEngine(const NodesCallGraph &dcg, std::string reachabilityExpression,
                       bool eliminateAnnotations = false);
    ReachabilityResult next(ReachabilityEngineState *, const DCGVertexType *);
    const NodesCallGraph &getDCG();
 
 protected:
    void annotationToStatements(const DCGVertexType *node,
                                std::unordered_set<const DCGVertexType *> &s);
    void addTransition(const DCGVertexType *, const std::unordered_set<const DCGVertexType *> &);
    std::unordered_set<const DCGVertexType *> getName(std::string name);
    const IR::Expression *getCondition(const DCGVertexType *);
    const IR::Expression *addCondition(const IR::Expression *prev,
                                       const DCGVertexType *currentState);
    static const IR::Expression *stringToNode(std::string name);
 
 protected:
    void addEdge(const DCGVertexType *vertex, IR::ID vertexName = IR::ID());
};
 
}  // namespace P4Tools
 
#endif /* COMMON_COMPILER_REACHABILITY_H_ */