SVF::POCRHybridSolver Class Reference

Solver Utilize Hybrid Representation of Graph. More...

#include <CFLSolver.h>

Inheritance diagram for SVF::POCRHybridSolver:

Classes
struct	TreeNode

Public Member Functions
bool	hasInd_h (NodeID src, NodeID dst)
TreeNode *	addInd_h (NodeID src, NodeID dst)
	Add a node dst to tree(src) More...
TreeNode *	getNode_h (NodeID src, NodeID dst)
	Get the node dst in tree(src) More...
void	insertEdge_h (TreeNode *u, TreeNode *v)
	add v into desc(x) as a child of u More...
void	addArc_h (NodeID src, NodeID dst)
void	meld_h (NodeID x, TreeNode *uNode, TreeNode *vNode)
	POCRHybridSolver (CFLGraph *_graph, CFGrammar *_grammar)
virtual	~POCRHybridSolver ()
	Destructor. More...
virtual void	processCFLEdge (const CFLEdge *Y_edge)
	Process CFLEdge. More...
virtual void	initialize ()
	Initialize worklist. More...
void	addArc (NodeID src, NodeID dst)
void	meld (NodeID x, TreeNode *uNode, TreeNode *vNode)
Public Member Functions inherited from SVF::POCRSolver
virtual void	clear ()
const_iterator	begin () const
const_iterator	end () const
iterator	begin ()
iterator	end ()
DataMap &	getSuccMap ()
DataMap &	getPredMap ()
TypeMap &	getSuccMap (const NodeID key)
TypeMap &	getPredMap (const NodeID key)
NodeBS &	getSuccs (const NodeID key, const Label ty)
NodeBS &	getPreds (const NodeID key, const Label ty)
bool	addEdge (const NodeID src, const NodeID dst, const Label ty)
NodeBS	addEdges (const NodeID src, const NodeBS &dstData, const Label ty)
	add edges and return the set of added edges (dst) for src More...
NodeBS	addEdges (const NodeBS &srcData, const NodeID dst, const Label ty)
	add edges and return the set of added edges (src) for dst More...
bool	hasEdge (const NodeID src, const NodeID dst, const Label ty)
	find src -> find src[ty] -> find dst in set More...
void	clearEdges (const NodeID key)
	POCRSolver (CFLGraph *_graph, CFGrammar *_grammar)
virtual	~POCRSolver ()
	Destructor. More...
virtual void	buildCFLData ()
	Init CFLData. More...
Public Member Functions inherited from SVF::CFLSolver
	CFLSolver (CFLGraph *_graph, CFGrammar *_grammar)
virtual	~CFLSolver ()
virtual void	solve ()
	Start solving. More...
const CFLGraph *	getGraph () const
	Return CFL Graph. More...
const CFGrammar *	getGrammar () const
	Return CFL Grammar. More...
virtual bool	pushIntoWorklist (const CFLEdge *item)
virtual bool	isWorklistEmpty ()

Public Attributes
Map< NodeID, std::unordered_map< NodeID, TreeNode * > >	indMap

Additional Inherited Members
Public Types inherited from SVF::POCRSolver
typedef std::map< const Label, NodeBS >	TypeMap
typedef std::unordered_map< NodeID, TypeMap >	DataMap
typedef DataMap::iterator	iterator
typedef DataMap::const_iterator	const_iterator
Public Types inherited from SVF::CFLSolver
typedef FIFOWorkList< const CFLEdge * >	WorkList
	Define worklist. More...
typedef CFGrammar::Production	Production
typedef CFGrammar::Symbol	Symbol
Static Public Attributes inherited from SVF::CFLSolver
static double	numOfChecks = 0
Protected Member Functions inherited from SVF::POCRSolver
bool	addPred (const NodeID key, const NodeID src, const Label ty)
bool	addSucc (const NodeID key, const NodeID dst, const Label ty)
bool	addPreds (const NodeID key, const NodeBS &data, const Label ty)
bool	addSuccs (const NodeID key, const NodeBS &data, const Label ty)
Protected Member Functions inherited from SVF::CFLSolver
const CFLEdge *	popFromWorklist ()
	Worklist operations. More...
bool	isInWorklist (const CFLEdge *item)
Protected Attributes inherited from SVF::POCRSolver
DataMap	succMap
DataMap	predMap
const NodeBS	emptyData
NodeBS	diff
Protected Attributes inherited from SVF::CFLSolver
CFLGraph *	graph
CFGrammar *	grammar
WorkList	worklist
	Worklist for resolution. More...

Detailed Description

Solver Utilize Hybrid Representation of Graph.

Hybrid graph representation for transitive relations The implementation is based on Yuxiang Lei, Yulei Sui, Shuo Ding, and Qirun Zhang. Taming Transitive Redundancy for Context-Free Language Reachability. ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications

Definition at line 294 of file CFLSolver.h.

Constructor & Destructor Documentation

POCRHybridSolver()

SVF::POCRHybridSolver::POCRHybridSolver ( CFLGraph *  _graph, CFGrammar *  _grammar  )

inline

Definition at line 347 of file CFLSolver.h.

                                                            : POCRSolver(_graph, _grammar)
    {
    }

~POCRHybridSolver()

virtual SVF::POCRHybridSolver::~POCRHybridSolver ( )

inlinevirtual

Destructor.

Definition at line 351 of file CFLSolver.h.

    {
        for (auto iter1: indMap)
        {
            for (auto iter2: iter1.second)
            {
                delete iter2.second;
                iter2.second = NULL;
            }
        }
    }

Member Function Documentation

addArc()

void POCRHybridSolver::addArc	(	NodeID	src,
		NodeID	dst
	)

Definition at line 314 of file CFLSolver.cpp.

{
    if(hasEdge(src, dst, grammar->strToSymbol("F")))
        return;
 
    for (auto& iter: indMap[src])
    {
        meld(iter.first, getNode_h(iter.first, src), getNode_h(dst, dst));
    }
}

addArc_h()

void POCRHybridSolver::addArc_h	(	NodeID	src,
		NodeID	dst
	)

Definition at line 359 of file CFLSolver.cpp.

{
    if (!hasInd_h(src, dst))
    {
        for (auto iter: indMap[src])
        {
            meld_h(iter.first, getNode_h(iter.first, src), getNode_h(dst, dst));
        }
    }
}

addInd_h()

POCRHybridSolver::TreeNode * POCRHybridSolver::addInd_h	(	NodeID	src,
		NodeID	dst
	)

Add a node dst to tree(src)

Definition at line 349 of file CFLSolver.cpp.

{
    TreeNode* newNode = new TreeNode(dst);
    auto resIns = indMap[dst].insert(std::make_pair(src, newNode));
    if (resIns.second)
        return resIns.first->second;
    delete newNode;
    return nullptr;
}

getNode_h()

TreeNode* SVF::POCRHybridSolver::getNode_h ( NodeID  src, NodeID  dst  )

inline

Get the node dst in tree(src)

Definition at line 331 of file CFLSolver.h.

    {
        return indMap[dst][src];
    }

hasInd_h()

bool POCRHybridSolver::hasInd_h	(	NodeID	src,
		NodeID	dst
	)

Definition at line 341 of file CFLSolver.cpp.

{
    auto it = indMap.find(dst);
    if (it == indMap.end())
        return false;
    return (it->second.find(src) != it->second.end());
}

initialize()

void POCRHybridSolver::initialize ( )

virtual

Initialize worklist.

add X(i,i) if not exist to E and to worklist

Foreach production X -> epsilon add X(i,i) if not exist to E and to worklist

Foreach production X -> epsilon add X(i,i) if not exist to E and to worklist

Reimplemented from SVF::POCRSolver.

Definition at line 284 of file CFLSolver.cpp.

{
    for(auto edge : graph->getCFLEdges())
    {
        pushIntoWorklist(edge);
    }
 
    // init hybrid dataset
    for (auto it = graph->begin(); it != graph->end(); ++it)
    {
        NodeID nId = it->first;
        addInd_h(nId, nId);
    }
 
    for(const Production& prod : grammar->getEpsilonProds())
    {
        for(auto IDMap : getSuccMap())
        {
            Symbol X = grammar->getLHSSymbol(prod);
            if (addEdge(IDMap.first, IDMap.first, X))
            {
                CFLNode* i = graph->getGNode(IDMap.first);
                const CFLEdge* newEdge = graph->addCFLEdge(i, i, X);
                pushIntoWorklist(newEdge);
            }
        }
    }
}

insertEdge_h()

void SVF::POCRHybridSolver::insertEdge_h ( TreeNode *  u, TreeNode *  v  )

inline

add v into desc(x) as a child of u

Definition at line 337 of file CFLSolver.h.

    {
        u->children.insert(v);
    }

meld()

void POCRHybridSolver::meld	(	NodeID	x,
		TreeNode *	uNode,
		TreeNode *	vNode
	)

Definition at line 326 of file CFLSolver.cpp.

{
    numOfChecks++;
 
    TreeNode* newVNode = addInd_h(x, vNode->id);
    if (!newVNode)
        return;
 
    insertEdge_h(uNode, newVNode);
    for (TreeNode* vChild: vNode->children)
    {
        meld_h(x, newVNode, vChild);
    }
}

meld_h()

void POCRHybridSolver::meld_h	(	NodeID	x,
		TreeNode *	uNode,
		TreeNode *	vNode
	)

Definition at line 370 of file CFLSolver.cpp.

{
    TreeNode* newVNode = addInd_h(x, vNode->id);
    if (!newVNode)
        return;
 
    insertEdge_h(uNode, newVNode);
    for (TreeNode* vChild: vNode->children)
    {
        meld_h(x, newVNode, vChild);
    }
}

processCFLEdge()

void POCRHybridSolver::processCFLEdge ( const CFLEdge *  Y_edge )

virtual

Process CFLEdge.

For each production X -> Y add X(i,j) if not exist to E and to worklist

For each production X -> Y Z Foreach outgoing edge Z(j,k) from node j do add X(i,k) if not exist to E and to worklist

For each production X -> Z Y Foreach incoming edge Z(k,i) to node i do add X(k,j) if not exist to E and to worklist

Reimplemented from SVF::POCRSolver.

Definition at line 216 of file CFLSolver.cpp.

{
    CFLNode* i = Y_edge->getSrcNode();
    CFLNode* j = Y_edge->getDstNode();
 
    Symbol Y = Y_edge->getEdgeKind();
    if (grammar->hasProdsFromSingleRHS(Y))
        for(const Production& prod : grammar->getProdsFromSingleRHS(Y))
        {
            Symbol X = grammar->getLHSSymbol(prod);
            numOfChecks++;
            if (addEdge(i->getId(), j->getId(), X))
            {
                const CFLEdge* newEdge = graph->addCFLEdge(Y_edge->getSrcNode(), Y_edge->getDstNode(), X);
                pushIntoWorklist(newEdge);
            }
 
        }
 
    if (grammar->hasProdsFromFirstRHS(Y))
        for(const Production& prod : grammar->getProdsFromFirstRHS(Y))
        {
            if ((grammar->getLHSSymbol(prod) == grammar->strToSymbol("F")) && (Y == grammar->strToSymbol("F")) && (grammar->getSecondRHSSymbol(prod) == grammar->strToSymbol("F")))
            {
                addArc(i->getId(), j->getId());
            }
            else
            {
                Symbol X = grammar->getLHSSymbol(prod);
                NodeBS diffDsts = addEdges(i->getId(), getSuccMap(j->getId())[grammar->getSecondRHSSymbol(prod)], X);
                numOfChecks += getSuccMap(j->getId())[grammar->getSecondRHSSymbol(prod)].count();
                for (NodeID diffDst: diffDsts)
                {
                    const CFLEdge* newEdge = graph->addCFLEdge(i, graph->getGNode(diffDst), X);
                    pushIntoWorklist(newEdge);
                }
            }
        }
 
    if(grammar->hasProdsFromSecondRHS(Y))
        for(const Production& prod : grammar->getProdsFromSecondRHS(Y))
        {
            if ((grammar->getLHSSymbol(prod) == grammar->strToSymbol("F")) && (Y == grammar->strToSymbol("F")) && (grammar->getFirstRHSSymbol(prod) == grammar->strToSymbol("F")))
            {
                addArc(i->getId(), j->getId());
            }
            else
            {
                Symbol X = grammar->getLHSSymbol(prod);
                NodeBS diffSrcs = addEdges(getPredMap(i->getId())[grammar->getFirstRHSSymbol(prod)], j->getId(), X);
                numOfChecks += getPredMap(i->getId())[grammar->getFirstRHSSymbol(prod)].count();
                for (NodeID diffSrc: diffSrcs)
                {
                    const CFLEdge* newEdge = graph->addCFLEdge(graph->getGNode(diffSrc), j, X);
                    pushIntoWorklist(newEdge);
                }
            }
        }
}

Member Data Documentation

indMap

Map<NodeID, std::unordered_map<NodeID, TreeNode*> > SVF::POCRHybridSolver::indMap

Definition at line 323 of file CFLSolver.h.

---

The documentation for this class was generated from the following files:

• /home/runner/work/SVF/SVF/svf/include/CFL/CFLSolver.h
• /home/runner/work/SVF/SVF/svf/lib/CFL/CFLSolver.cpp