SVF::CFLSolver Class Reference

#include <CFLSolver.h>

Inheritance diagram for SVF::CFLSolver:

Public Types
typedef FIFOWorkList< const CFLEdge * >	WorkList
	Define worklist. More...
typedef CFGrammar::Production	Production
typedef CFGrammar::Symbol	Symbol

Public Member Functions
	CFLSolver (CFLGraph *_graph, CFGrammar *_grammar)
virtual	~CFLSolver ()
virtual void	initialize ()
	Initialize worklist. More...
virtual void	processCFLEdge (const CFLEdge *Y_edge)
	Process CFLEdge. More...
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 ()

Static Public Attributes
static double	numOfChecks = 0

Protected Member Functions
const CFLEdge *	popFromWorklist ()
	Worklist operations. More...
bool	isInWorklist (const CFLEdge *item)

Protected Attributes
CFLGraph *	graph
CFGrammar *	grammar
WorkList	worklist
	Worklist for resolution. More...

Detailed Description

Definition at line 43 of file CFLSolver.h.

Member Typedef Documentation

Production

typedef CFGrammar::Production SVF::CFLSolver::Production

Definition at line 49 of file CFLSolver.h.

Symbol

typedef CFGrammar::Symbol SVF::CFLSolver::Symbol

Definition at line 50 of file CFLSolver.h.

WorkList

typedef FIFOWorkList<const CFLEdge*> SVF::CFLSolver::WorkList

Define worklist.

Definition at line 48 of file CFLSolver.h.

Constructor & Destructor Documentation

CFLSolver()

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

inline

Definition at line 54 of file CFLSolver.h.

                                                    : graph(_graph), grammar(_grammar)
    {
    }

~CFLSolver()

virtual SVF::CFLSolver::~CFLSolver ( )

inlinevirtual

Definition at line 58 of file CFLSolver.h.

    {
        delete graph;
        delete grammar;
    }

Member Function Documentation

getGrammar()

const CFGrammar* SVF::CFLSolver::getGrammar ( ) const

inline

Return CFL Grammar.

Definition at line 80 of file CFLSolver.h.

    {
        return grammar;
    }

getGraph()

const CFLGraph* SVF::CFLSolver::getGraph ( ) const

inline

Return CFL Graph.

Definition at line 74 of file CFLSolver.h.

    {
        return graph;
    }

initialize()

void CFLSolver::initialize ( )

virtual

Initialize worklist.

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

Reimplemented in SVF::POCRHybridSolver, and SVF::POCRSolver.

Definition at line 36 of file CFLSolver.cpp.

{
    for(auto it = graph->begin(); it!= graph->end(); it++)
    {
        for(const CFLEdge* edge : (*it).second->getOutEdges())
        {
            pushIntoWorklist(edge);
        }
    }
 
    for(const Production& prod : grammar->getEpsilonProds())
    {
        for(auto it = graph->begin(); it!= graph->end(); it++)
        {
            Symbol X = grammar->getLHSSymbol(prod);
            CFLNode* i = (*it).second;
            if(const CFLEdge* edge = graph->addCFLEdge(i, i, X))
            {
                pushIntoWorklist(edge);
            }
        }
    }
}

isInWorklist()

bool SVF::CFLSolver::isInWorklist ( const CFLEdge *  item )

inlineprotected

Definition at line 101 of file CFLSolver.h.

    {
        return worklist.find(item);
    }

isWorklistEmpty()

virtual bool SVF::CFLSolver::isWorklistEmpty ( )

inlinevirtual

Definition at line 88 of file CFLSolver.h.

    {
        return worklist.empty();
    }

popFromWorklist()

const CFLEdge* SVF::CFLSolver::popFromWorklist ( )

inlineprotected

Worklist operations.

Definition at line 96 of file CFLSolver.h.

    {
        return worklist.pop();
    }

processCFLEdge()

void CFLSolver::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 in SVF::POCRHybridSolver, and SVF::POCRSolver.

Definition at line 62 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(const CFLEdge* newEdge = graph->addCFLEdge(i, j, X))
            {
                pushIntoWorklist(newEdge);
            }
        }
 
    if (grammar->hasProdsFromFirstRHS(Y))
        for(const Production& prod : grammar->getProdsFromFirstRHS(Y))
        {
            Symbol X = grammar->getLHSSymbol(prod);
            for(const CFLEdge* Z_edge : j->getOutEdgeWithTy(grammar->getSecondRHSSymbol(prod)))
            {
                CFLNode* k = Z_edge->getDstNode();
                numOfChecks++;
                if(const CFLEdge* newEdge = graph->addCFLEdge(i, k, X))
                {
                    pushIntoWorklist(newEdge);
                }
            }
        }
 
    if(grammar->hasProdsFromSecondRHS(Y))
        for(const Production& prod : grammar->getProdsFromSecondRHS(Y))
        {
            Symbol X = grammar->getLHSSymbol(prod);
            for(const CFLEdge* Z_edge : i->getInEdgeWithTy(grammar->getFirstRHSSymbol(prod)))
            {
                CFLNode* k = Z_edge->getSrcNode();
                numOfChecks++;
                if(const CFLEdge* newEdge = graph->addCFLEdge(k, j, X))
                {
                    pushIntoWorklist(newEdge);
                }
            }
        }
}

pushIntoWorklist()

virtual bool SVF::CFLSolver::pushIntoWorklist ( const CFLEdge *  item )

inlinevirtual

Definition at line 84 of file CFLSolver.h.

    {
        return worklist.push(item);
    }

solve()

void CFLSolver::solve ( )

virtual

Start solving.

initial worklist

Select and remove an edge Y(i,j) from worklist

Definition at line 119 of file CFLSolver.cpp.

{
    initialize();
 
    while(!isWorklistEmpty())
    {
        const CFLEdge* Y_edge = popFromWorklist();
        processCFLEdge(Y_edge);
    }
}

Member Data Documentation

grammar

CFGrammar* SVF::CFLSolver::grammar

protected

Definition at line 109 of file CFLSolver.h.

graph

CFLGraph* SVF::CFLSolver::graph

protected

Definition at line 108 of file CFLSolver.h.

numOfChecks

double CFLSolver::numOfChecks = 0

static

Definition at line 52 of file CFLSolver.h.

worklist

WorkList SVF::CFLSolver::worklist

protected

Worklist for resolution.

Definition at line 111 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