CFLSolver.h

Go to the documentation of this file.

//===----- CFLSolver.h -- Context-free language reachability solver--------------//
//
//                     SVF: Static Value-Flow Analysis
//
// Copyright (C) <2013->  <Yulei Sui>
//
 
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
 
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Affero General Public License for more details.
 
// You should have received a copy of the GNU Affero General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
//
//===----------------------------------------------------------------------===//
 
/*
 * CFLSolver.h
 *
 *  Created on: March 5, 2022
 *      Author: Yulei Sui， Yuxiang Lei
 */
 
#ifndef INCLUDE_CFL_CFLSolver_H_
#define INCLUDE_CFL_CFLSolver_H_
 
#include "Graphs/CFLGraph.h"
#include "CFL/CFGrammar.h"
#include "Util/WorkList.h"
 
using namespace std;
 
namespace SVF
{
typedef GrammarBase::Symbol Label;
 
class CFLSolver
{
 
public:
    typedef FIFOWorkList<const CFLEdge*> WorkList;
    typedef CFGrammar::Production Production;
    typedef CFGrammar::Symbol Symbol;
 
    static double numOfChecks;
 
    CFLSolver(CFLGraph* _graph, CFGrammar* _grammar): graph(_graph), grammar(_grammar)
    {
    }
 
    virtual ~CFLSolver()
    {
        delete graph;
        delete grammar;
    }
 
    virtual void initialize();
 
    virtual void processCFLEdge(const CFLEdge* Y_edge);
 
    virtual void solve();
 
    inline const CFLGraph* getGraph() const
    {
        return graph;
    }
 
    inline const CFGrammar* getGrammar() const
    {
        return grammar;
    }
    virtual inline bool pushIntoWorklist(const CFLEdge* item)
    {
        return worklist.push(item);
    }
    virtual inline bool isWorklistEmpty()
    {
        return worklist.empty();
    }
 
protected:
 
    inline const CFLEdge* popFromWorklist()
    {
        return worklist.pop();
    }
 
    inline bool isInWorklist(const CFLEdge* item)
    {
        return worklist.find(item);
    }
 
protected:
    CFLGraph* graph;
    CFGrammar* grammar;
    WorkList worklist;
 
};
 
class POCRSolver : public CFLSolver
{
public:
    typedef std::map<const Label, NodeBS> TypeMap;                  // Label with SparseBitVector of NodeID
    typedef std::unordered_map<NodeID, TypeMap> DataMap;            // Each Node has a TypeMap
    typedef typename DataMap::iterator iterator;                    // iterator for each node
    typedef typename DataMap::const_iterator const_iterator;
 
protected:
    DataMap succMap;                                                // succ map for nodes contains Label: Edgeset
    DataMap predMap;                                                // pred map for nodes contains Label: edgeset
    const NodeBS emptyData;                                         // ??
    NodeBS diff;
    // union/add data
    inline bool addPred(const NodeID key, const NodeID src, const Label ty)
    {
        return predMap[key][ty].test_and_set(src);
    };
 
    inline bool addSucc(const NodeID key, const NodeID dst, const Label ty)
    {
        return succMap[key][ty].test_and_set(dst);
    };
 
    inline bool addPreds(const NodeID key, const NodeBS& data, const Label ty)
    {
        if (data.empty())
            return false;
        return predMap[key][ty] |= data;                            // union of sparsebitvector (add to LHS)
    }
 
    inline bool addSuccs(const NodeID key, const NodeBS& data, const Label ty)
    {
        if (data.empty())
            return false;
        return succMap[key][ty] |= data;                            // // union of sparsebitvector (add to LHS)
    }
public:
 
    virtual void clear()
    {
        succMap.clear();
        predMap.clear();
    }
 
    inline const_iterator begin() const
    {
        return succMap.begin();
    }
 
    inline const_iterator end() const
    {
        return succMap.end();
    }
 
    inline iterator begin()
    {
        return succMap.begin();
    }
 
    inline iterator end()
    {
        return succMap.end();
    }
 
    inline DataMap& getSuccMap()
    {
        return succMap;
    }
 
    inline DataMap& getPredMap()
    {
        return predMap;
    }
 
    inline TypeMap& getSuccMap(const NodeID key)
    {
        return succMap[key];
    }
 
    inline TypeMap& getPredMap(const NodeID key)
    {
        return predMap[key];
    }
 
    inline NodeBS& getSuccs(const NodeID key, const Label ty)
    {
        return succMap[key][ty];
    }
 
    inline NodeBS& getPreds(const NodeID key, const Label ty)
    {
        return predMap[key][ty];
    }
 
    // Alias data operations
    inline bool addEdge(const NodeID src, const NodeID dst, const Label ty)
    {
        addSucc(src, dst, ty);
        return addPred(dst, src, ty);
    }
 
    inline NodeBS addEdges(const NodeID src, const NodeBS& dstData, const Label ty)
    {
        NodeBS newDsts;
        if (addSuccs(src, dstData, ty))
        {
            for (const NodeID datum: dstData)
                if (addPred(datum, src, ty))
                    newDsts.set(datum);
        }
        return newDsts;
    }
 
    inline NodeBS addEdges(const NodeBS& srcData, const NodeID dst, const Label ty)
    {
        NodeBS newSrcs;
        if (addPreds(dst, srcData, ty))
        {
            for (const NodeID datum: srcData)
                if (addSucc(datum, dst, ty))
                    newSrcs.set(datum);
        }
        return newSrcs;
    }
 
    inline bool hasEdge(const NodeID src, const NodeID dst, const Label ty)
    {
        const_iterator iter1 = succMap.find(src);
        if (iter1 == succMap.end())
            return false;
 
        auto iter2 = iter1->second.find(ty);
        if (iter2 == iter1->second.end())
            return false;
 
        return iter2->second.test(dst);
    }
 
    /* This is a dataset version, to be modified to a cflData version */
    inline void clearEdges(const NodeID key)
    {
        succMap[key].clear();
        predMap[key].clear();
    }
 
    POCRSolver(CFLGraph* _graph, CFGrammar* _grammar) : CFLSolver(_graph, _grammar)
    {
        buildCFLData();
    }
    virtual ~POCRSolver()
    {
    }
 
    virtual void processCFLEdge(const CFLEdge* Y_edge);
 
    virtual void buildCFLData();
 
    virtual void initialize();
};
class POCRHybridSolver : public POCRSolver
{
//Hybrid
//{@
public:
    struct TreeNode
    {
        NodeID id;
        std::unordered_set<TreeNode*> children;
 
        TreeNode(NodeID nId) : id(nId)
        {}
 
        ~TreeNode()
        {
        }
 
        inline bool operator==(const TreeNode& rhs) const
        {
            return id == rhs.id;
        }
 
        inline bool operator<(const TreeNode& rhs) const
        {
            return id < rhs.id;
        }
    };
 
public:
    Map<NodeID, std::unordered_map<NodeID, TreeNode*>> indMap;   // indMap[v][u] points to node v in tree(u)
 
    bool hasInd_h(NodeID src, NodeID dst);
 
    TreeNode* addInd_h(NodeID src, NodeID dst);
 
    TreeNode* getNode_h(NodeID src, NodeID dst)
    {
        return indMap[dst][src];
    }
 
    void insertEdge_h(TreeNode* u, TreeNode* v)
    {
        u->children.insert(v);
    }
 
    void addArc_h(NodeID src, NodeID dst);
 
    void meld_h(NodeID x, TreeNode* uNode, TreeNode* vNode);
public:
    POCRHybridSolver(CFLGraph* _graph, CFGrammar* _grammar) : POCRSolver(_graph, _grammar)
    {
    }
    virtual ~POCRHybridSolver()
    {
        for (auto iter1: indMap)
        {
            for (auto iter2: iter1.second)
            {
                delete iter2.second;
                iter2.second = NULL;
            }
        }
    }
 
    virtual void processCFLEdge(const CFLEdge* Y_edge);
 
    virtual void initialize();
 
public:
    void addArc(NodeID src, NodeID dst);
    void meld(NodeID x, TreeNode* uNode, TreeNode* vNode);
};
}
 
#endif /* INCLUDE_CFL_CFLSolver_H_*/