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)

TreeNode *	getNode_h (NodeID src, NodeID dst)
	Get the node dst in tree(src)

void	insertEdge_h (TreeNode u, TreeNode v)
	add v into desc(x) as a child of u

void	addArc_h (NodeID src, NodeID dst)

void	meld_h (NodeID x, TreeNode uNode, TreeNode vNode)

	POCRHybridSolver (CFLGraph _graph, CFGrammar _grammar)

virtual	~POCRHybridSolver ()
	Destructor.

virtual void	processCFLEdge (const CFLEdge *Y_edge)
	Process CFLEdge.

virtual void	initialize ()
	Initialize worklist.

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

NodeBS	addEdges (const NodeBS &srcData, const NodeID dst, const Label ty)
	add edges and return the set of added edges (src) for dst

bool	hasEdge (const NodeID src, const NodeID dst, const Label ty)
	find src -> find src[ty] -> find dst in set

void	clearEdges (const NodeID key)

	POCRSolver (CFLGraph _graph, CFGrammar _grammar)

virtual	~POCRSolver ()
	Destructor.

virtual void	buildCFLData ()
	Init CFLData.

Public Member Functions inherited from SVF::CFLSolver
	CFLSolver (CFLGraph _graph, CFGrammar _grammar)

virtual	~CFLSolver ()

virtual void	solve ()
	Start solving.

const CFLGraph *	getGraph () const
	Return CFL Graph.

const CFGrammar *	getGrammar () const
	Return CFL Grammar.

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.

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.

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.

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 295 of file CFLSolver.h.

Constructor & Destructor Documentation

◆ POCRHybridSolver()

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

inline

Definition at line 348 of file CFLSolver.h.

                                                            : POCRSolver(_graph, _grammar)
    {
    }

◆ ~POCRHybridSolver()

virtual SVF::POCRHybridSolver::~POCRHybridSolver ( )

inlinevirtual

Destructor.

Definition at line 352 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 332 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

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 338 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 324 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

Classes

Public Member Functions

Public Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ POCRHybridSolver()

◆ ~POCRHybridSolver()

Member Function Documentation

◆ addArc()

◆ addArc_h()

◆ addInd_h()

◆ getNode_h()

◆ hasInd_h()

◆ initialize()

◆ insertEdge_h()

◆ meld()

◆ meld_h()

◆ processCFLEdge()

Member Data Documentation

◆ indMap